/* {{{1
KCChess -- yet another xboard-compatible chess engine.
Copyright (C) 2006-2007 Konstantin 'KCC' Serebryany <konstantin.s.serebryany#gmail.com>

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.

*/

//# INCLUDES {{{1
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <deque>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <string> 
#include <time.h>

#include <map>
#include <set>
using namespace std;

// hash_map and hash_set are not part of C++ std yet. 
#include <ext/hash_map>
#include <ext/hash_set>
using namespace __gnu_cxx;

#include <stdint.h>
#include <unistd.h>

//#include <jthread/jthread.h> //http://research.edm.uhasselt.be/jori/jthread/jthread.html 

#include "kcchess.h"

namespace KCChess{


//# DEBUG {{{1
#ifndef DEBUG
# define DEBUG 1
#endif

#if DEBUG >= 1
# define Assert assert
#else
# define Assert(a) 
#endif


#if DEBUG >= 1
# define DO_DEBUG(cond, action) do{if(cond){action;}}while(0)
# define DEBUG_DECL(decl) decl
#else
# define DO_DEBUG(cond, action)
# define DEBUG_DECL(decl)
#endif


//# TABLE of CONSTANTS {{{1
struct CONSTANT_TABLE{
    typedef BB BB64[64];
    // N_attacks[i][pos] is set if a knight in position 'pos' attacks position 'i'
    BB64 N_attacks;
    // K_attacks[i][pos] similar to N_attacks, but for King
    BB64 K_attacks;

    // D_P_attacks[i][pos] similar to N_attacks, but for dark pawns 
    BB64 D_P_attacks;
    // L_P_attacks[i][pos] similar to N_attacks, but for light pawns 
    BB64 L_P_attacks;

    /// N_attacks_count[i] = N_attacks[i].popcnt()
    int64_t N_attacks_count[64];


    // moves of white pawn
    BB64 L_P_moves; 



    // r -- right
    // l -- left
    // u -- up
    // d -- down
    // ru -- right and up
    // rd, lu, ld
    struct BB_RLUD{
        BB r, l, u, d, ru, rd, lu, ld;
    };
    
    BB_RLUD slide[64];
    BB  wave[64][8];


    BB rows_3456;
    BB rows_23456;
    BB row_2; 
    BB row_7;

    BB cols[8];


    static const bb_t random_values[4096];


    score_t opening_bonus_K[64];
    score_t opening_bonus_N[64];
    score_t opening_bonus_B[64];

    CONSTANT_TABLE();
    

};

/// Construct the table 
CONSTANT_TABLE::CONSTANT_TABLE()
{
    const int N_moves_r[] = {2, 2, 1, 1, -1, -1, -2, -2};
    const int N_moves_c[] = {1, -1, 2, -2, 2, -2, 1, -1};

    const int K_moves_r[] = {+1, +1, +1, +0, +0, -1, -1, -1};
    const int K_moves_c[] = {-1, +0, +1, +1, -1, -1, +0, +1};

    memset((void*)this, 0, sizeof(*this));

    BB bb;

    for(int i = 0; i < 64; i++){
        POS pos(i);

        // N_attacks
        bb = 0;
        for(int j = 0; j < 8; j++){
            pos_off_t r = N_moves_r[j];
            pos_off_t c = N_moves_c[j];
            if(pos.shift_is_legal(r, c)) 
                bb.set(POS(pos, r, c));
        }
        N_attacks[i] = bb;
        N_attacks_count[i] = bb.popcnt();

        // K_attacks
        bb = 0;
        for(int j = 0; j < 8; j++){
            pos_off_t r = K_moves_r[j];
            pos_off_t c = K_moves_c[j];
            if(pos.shift_is_legal(r, c)) 
                bb.set(POS(pos, r, c));
        }
        K_attacks[i] = bb;


        // D_P_attacks
        bb = 0;
        if(pos.shift_is_legal(1, -1))      bb.set(POS(pos, 1, -1));
        if(pos.shift_is_legal(1, 1))       bb.set(POS(pos, 1, 1));
        D_P_attacks[i] = bb;
        // L_P_attacks
        bb = 0;
        if(pos.shift_is_legal(-1, -1))      bb.set(POS(pos, -1, -1));
        if(pos.shift_is_legal(-1, 1))       bb.set(POS(pos, -1, 1));
        L_P_attacks[i] = bb;

        // L_P_moves
        if(pos.row() < ROW_8)              L_P_moves[i].set(POS(pos, 1, 0));
        if(pos.row() == ROW_2)             L_P_moves[i].set(POS(pos, 2, 0));


        // slide
        for(int j = 1; j < 8; j++){
            int r, c;
            r = +j; c = +0; if(pos.shift_is_legal(r,c)) slide[i].u.set(POS(pos, r, c));
            r = -j; c = -0; if(pos.shift_is_legal(r,c)) slide[i].d.set(POS(pos, r, c));
            r = +0; c = +j; if(pos.shift_is_legal(r,c)) slide[i].r.set(POS(pos, r, c));
            r = -0; c = -j; if(pos.shift_is_legal(r,c)) slide[i].l.set(POS(pos, r, c));
            r = +j; c = +j; if(pos.shift_is_legal(r,c)) slide[i].ru.set(POS(pos, r, c));
            r = +j; c = -j; if(pos.shift_is_legal(r,c)) slide[i].lu.set(POS(pos, r, c));
            r = -j; c = +j; if(pos.shift_is_legal(r,c)) slide[i].rd.set(POS(pos, r, c));
            r = -j; c = -j; if(pos.shift_is_legal(r,c)) slide[i].ld.set(POS(pos, r, c));
        }


        // wave
        for(int j = 1; j <= 7; j++){
            BB &w = wave[i][j];
            int r, c;
            r = +j; c = +0; if(pos.shift_is_legal(r,c)) w.set(POS(pos, r, c));
            r = -j; c = -0; if(pos.shift_is_legal(r,c)) w.set(POS(pos, r, c));
            r = +0; c = +j; if(pos.shift_is_legal(r,c)) w.set(POS(pos, r, c));
            r = -0; c = -j; if(pos.shift_is_legal(r,c)) w.set(POS(pos, r, c));
            r = +j; c = +j; if(pos.shift_is_legal(r,c)) w.set(POS(pos, r, c));
            r = +j; c = -j; if(pos.shift_is_legal(r,c)) w.set(POS(pos, r, c));
            r = -j; c = +j; if(pos.shift_is_legal(r,c)) w.set(POS(pos, r, c));
            r = -j; c = -j; if(pos.shift_is_legal(r,c)) w.set(POS(pos, r, c));

            if(j > 1)
                w = w | wave[i][j-1];
        }

        // rows_3456
        if(pos.row() >= ROW_2 && pos.row() <= ROW_6){
            rows_3456.set(pos);
        }
        // row_2
        if(pos.row() == ROW_2){
            row_2.set(pos);
        }
        rows_23456 = rows_3456 | row_2;
        // row_7
        if(pos.row() == ROW_7){
            row_7.set(pos);
        }

        cols[pos.col()].set(pos);

        // init bonus values
        const score_t OPB_K[64] = {
            0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 5, 0, 0, 0, 8, 0,
        };

        const score_t OPB_N[64] = {
            0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 1, 1, 1, 1, 0, 0,
            0, 0, 1, 2, 2, 1, 0, 0,
            0, 0, 2, 1, 1, 2, 0, 0,
            0, 0, 1, 1, 1, 1, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0,
        };

        const score_t OPB_B[64] = {
            0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0,
            0, 1, 0, 0, 0, 0, 1, 0,
            0, 0, 2, 0, 0, 2, 0, 0,
            0, 0, 0, 2, 2, 0, 0, 0,
            0, 2, 0, 1, 1, 0, 2, 0,
            0, 0, 0, 0, 0, 0, 0, 0,
        };



        opening_bonus_K[pos] = OPB_K[pos.reflect()];
        opening_bonus_N[pos] = OPB_N[pos.reflect()];
        opening_bonus_B[pos] = OPB_B[pos.reflect()];

    }




}

/// Global constant table of constants 
static const CONSTANT_TABLE TABLE;

// {{{1 SCORE
const score_t SCORE::piece_score_arr[6] = 
{SCORE::SCORE_K, SCORE::SCORE_Q, SCORE::SCORE_R, SCORE::SCORE_B, SCORE::SCORE_N, SCORE::SCORE_P};

//# BOARD {{{1
#if DEBUG >= 1
# define AssertBoard(cond) do{if(!(cond)){show_board(cout << endl); Assert(cond);}}while(0);
#else
# define AssertBoard(cond) 
#endif

//# BOARD::show_board() {{{2
ostream &BOARD::show_board(ostream &os) const
{
    BOARD reflected = *this;
    reflected.reflect_in_place();
    const BOARD ar[2] = {*this, reflected};
    os << fen() << endl;
    show_boards(os, ar, ar+2);
    os << endl;
    os << "   A B C D E F G H    A B C D E F G H" << endl;
    return os;
}


//# GEN_MOVE_ACTION_STORE_CAPTURES_AND_PROMO {{{2
/**
    Action type for BOARD::gen_moves(): 
    - store all moves to positions in m_mask. 
    - store promo moves
  */
class GEN_MOVE_ACTION_STORE_CAPTURES_AND_PROMO :public GEN_MOVE_ACTION_STORE
{
    BB m_mask;
public: 
    GEN_MOVE_ACTION_STORE_CAPTURES_AND_PROMO(BB mask)
        :m_mask(mask) {}
    BB mask_target(BB b) {return b & m_mask;}
    bool allow_promo()      {return true;}
    bool allow_en_passant() {return false;}
};

//# MOVE_MAKER {{{2
/// Wrapper for BOARD::gen_moves()
class MOVE_MAKER{
    const bool m_count_only;
    const BOARD &board;
    size_t n_moves;
    MOVE::move_t legal_moves[MAX_N_MOVES];
public:
    BOARD moved_boards[MAX_N_MOVES];


    MOVE_MAKER(const BOARD &b)
        :m_count_only(false)
        ,board(b)
    {
        n_moves = 0;
//        MOVE::move_t pseudo_moves[MAX_N_MOVES];
        GEN_MOVE_ACTION_STORE pseudo_moves;
        size_t n_pseudo_moves = board.gen_moves(pseudo_moves);
//        cout << "MOVE_MAKER: " << n_pseudo_moves << endl;
//        board.show_board(cout);
        for(size_t i = 0; i < n_pseudo_moves; i++){
            BOARD new_board(board, pseudo_moves[i]);
            if(!new_board.ally_K_is_attacked()){
                new_board.reflect_in_place();
                legal_moves[n_moves] = pseudo_moves[i];
                moved_boards[n_moves] = new_board;
                n_moves++;
            }
        }
    }

    bool is_mate(){
        return (size() == 0 && board.ally_K_is_attacked());
    }

    size_t size() const {return n_moves;}
    MOVE operator [] (size_t i) {Assert(!m_count_only); return legal_moves[i];}

    int move_index(MOVE move) const{
        for(size_t i = 0; i < size(); i++){
            if(legal_moves[i] == move.raw())
                return i;
        }
        return -1;
    }

};

//# BOARD operator << {{{2
inline ostream &operator << (ostream &os, const BOARD &board)
{
    return board.show_board(os);
}

//# BOARD::fen() {{{2
/// Create a FEN string for the board
string BOARD::fen() const
{
    //"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -"
    BOARD t = *this;

    string res;

    bool is_reflected = false;
    if(t.is_reflected()){
        is_reflected = true;
        t.reflect_in_place();
    }

    for(int row = ROW_8; row >= ROW_1; row--){
        int empty = 0;
        for(int col = COL_A; col <= COL_H; col++){
            POS pos(row, col);
            if(t.get_occupied(pos)){
                PIECE piece = t.get_piece(pos);
                COLOR color = t.get_color(pos);
                if(empty){
                    res += (char)(empty + '0');
                    empty = 0;
                }
                res += (char)piece_to_char(piece, color);
            }else{
                empty++;
            }
        }
        if(empty)
            res += (char)(empty + '0');

        if(row != ROW_1)
            res += '/';
    }
    res += ' ';
    
    res += is_reflected ? "b" : "w"; 
    res += ' ';

    if(m_castling_info.raw() == 0){
        res += "-";
    }else{
        if(m_castling_info.L_K()) res += "K";
        if(m_castling_info.L_Q()) res += "Q";
        if(m_castling_info.D_K()) res += "k";
        if(m_castling_info.D_Q()) res += "q";
    }
    res += " ";


    if(!m_has_en_passant){
        res += "-";
    }else{
        res += ('a' + m_en_passant_column);
        res += is_reflected ? "3" : "6";
    }
    res += " ";


    return res;
}

//# BOARD::show_boards() {{{2
template <class ITER> 
ostream &BOARD::show_boards(ostream &os, ITER beg, ITER end)
{
//    os << "   ABCDEFGH" << endl << endl;
    for(int row = 7; row >= 0; row--){
        os << (row + 1) << "  " ;
        for(ITER i = beg; i != end; ++i){
            BOARD b = *i;
            for(int col = 0; col < 8; col++){
                POS pos(row,col);
                if(b.get_occupied(pos)){
                    PIECE piece = b.get_piece(pos);
                    COLOR color = b.get_color(pos);
                    os << (char)b.piece_to_char(piece, color) << " ";
                }else{
                    os << ". ";
                }
            }
            os << ((b.is_reflected() && row == 7) ? "%" : " ");
            os << "  ";
        }
        os << endl;
    }
    return os;
}

//# BOARD::make_SAN() {{{2
/// Print move in SAN format
ostream &BOARD::make_SAN(ostream &os, MOVE move) const
{
    // not a real SAN so far 
    os <<  (char)piece_to_char(get_piece(move.from()), L);
    if(is_reflected())
        move.reflect();
    os << move;
    return os; 
}

//# BOARD::parse_SAN() {{{2
/// Interpret a move in SAN format
MOVE BOARD::parse_SAN(const string &san) const
{
    MOVE_MAKER moves(*this);
    int i, n = moves.size();
    unsigned col, row; 
    PIECE promo = K;

    string SAN = san;

    // remove trailing +
    if(SAN.size() > 1 && SAN[SAN.size() - 1] == '+')
        SAN.resize(SAN.size()-1);
       
//    cout << "parse_SAN: " << SAN << endl;


    // check if we have =Q at the end
    if(SAN.size() > 2 && SAN[SAN.size()-2] == '='){
        char promo_char = SAN[SAN.size()-1];
        if      (promo_char == 'N'){ promo = N;
        }else if(promo_char == 'Q'){ promo = Q;
        }else if(promo_char == 'B'){ promo = B;
        }else if(promo_char == 'R'){ promo = R;
        }else{
            return 0 ;
        }
        SAN.resize(SAN.size()-2);
    }

    if(SAN.size() < 2)
        return 0;



    for(i = 0; i < n; i++){
        MOVE move = moves[i];
        PIECE piece = get_piece(move.from());
    
        // castling K side 
        if(SAN == "O-O" || SAN == "o-o" || SAN == "0-0"){
            if(piece == K && move.from() == E1 && move.to() == G1){
                return move;
            }
        }

        // castling Q side
        if(SAN == "O-O-O" || SAN == "o-o-o" || SAN == "0-0-0"){
            if(piece == K && move.from() == E1 && move.to() == C1){
                return move;
            }
        }

        // regular piece move, like Nb1 or Qxf3, Ngf3, N5xf3
        if( 
                (SAN[0] == 'K' && piece == K)
             || (SAN[0] == 'Q' && piece == Q)
             || (SAN[0] == 'R' && piece == R)
             || (SAN[0] == 'B' && piece == B)
             || (SAN[0] == 'N' && piece == N)
                ){
            int disamb = 0;
            if(SAN.size() == 3){
                col = SAN[1] - 'a';
                row = SAN[2] - '1';
            }else if(SAN.size() == 4 && SAN[1] == 'x'){
                col = SAN[2] - 'a';
                row = SAN[3] - '1';
            }else if(SAN.size() == 4){
                disamb = SAN[1];
                col = SAN[2] - 'a';
                row = SAN[3] - '1';
            }else if(SAN.size() == 5 && SAN[2] == 'x'){
                disamb = SAN[1];
                col = SAN[3] - 'a';
                row = SAN[4] - '1';
            }else{
                return 0;
            }   


            if(!(col < 8 && row < 8))
                return 0;

            if(is_reflected())
                row = 7 - row;


            if(disamb){
                // cout << move << (char)(disamb) << endl;
                if(disamb >= '1' && disamb <= '8'){
                    unsigned from_row = disamb - '1';
                    if(is_reflected())
                        from_row = 7 - from_row;
                    if(move.to() == POS(row, col) && move.from().row() == from_row)
                        return move;
                }else if(disamb >= 'a' && disamb <= 'h'){
                    unsigned from_col = disamb - 'a';
                    if(move.to() == POS(row, col) && move.from().col() == from_col)
                        return move;
                }
            }else{
                if(move.to() == POS(row, col))
                    return move;
            }
                    
        }

        // regular pawn move, like f5
        if(piece == P){
//            cout << "try: " <<  move << endl;
            unsigned from_col = 8;
            if(SAN.size() == 2){
                col = SAN[0] - 'a';
                row = SAN[1] - '1';
                from_col = col;
            }else if(SAN.size() == 4 && SAN[1] == 'x'){
                // pawn attack: dxe5
                col = SAN[2] - 'a';
                row = SAN[3] - '1';
                from_col = SAN[0] - 'a';
            }else{
                return 0;
            }

            if(is_reflected())
                row = 7 - row;
            if(col < 8 && row < 8){
                if(move.to() == POS(row, col) 
                        && from_col == move.from().col()
                        && move.get_promot_piece() == promo) 
                    return move;
            }
        }
    }
    return 0;
}

//# BOARD::read_fen() {{{2
/// Initialize the board from a sting in FEN format 
bool BOARD::read_fen(const string &fen, string &rest_of_string)
{
    int c;
    const char *fen_str = fen.c_str();
    clear();
    // rnbqkbnr/pp1ppppp/8/2p5/4P3/5N2/PPPP1PPP/RNBQKB1R b KQkq - 1 2
    if(!fen_str)
        return false;
    for(int row = 7; row >= 0; row--){
        int col = 0;
//        cerr << "zz " << __LINE__ << " " << fen_str << endl;
        while(col < 8){
            c = *(fen_str++);
            if(c >= '1' && c <= '8'){
                col += (c - '0');
                continue;
            }
            int piece = char_to_piece(c);
            if(piece == PIECE_ERROR){
                cerr << fen_str;
                return false;
            }
            set_piece(POS(row,col), piece, char_to_color(c));
            col++; 
            continue;
        }
        if(col != 8){
            cerr << fen_str;
            return false;
        }
        if(row != 0){
            if(*(fen_str++) != '/'){
                cerr << fen_str;
                return false;
            }
        }
    }
    // skip ws
    while(isspace(*(fen_str)))  fen_str++;
    
//    cerr << "zz " << __LINE__ << endl;
    // read move color
    char color = *(fen_str++);
    bool need_reflection = false;
    if(color == 'b'){
        need_reflection = true;
    }else if(color != 'w'){
        cerr << fen_str;
        return false;
    }

    // skip ws
    while(isspace(*(fen_str)))  fen_str++;
    
    // read castling
    if(*fen_str == '-'){
        fen_str++;
    }else{
        while(!isspace(c = *fen_str++)){
            /**/ if(c == 'k') { m_castling_info.set_D_K();}
            else if(c == 'K') { m_castling_info.set_L_K();}
            else if(c == 'q') { m_castling_info.set_D_Q();}
            else if(c == 'Q') { m_castling_info.set_L_Q();}
            else return false;
        }
    }
    
    // skip ws
    while(isspace(*(fen_str)))  fen_str++;

    // read enpassant 
    if(*fen_str == '-'){
        fen_str++;
    }else{
        int col = *(fen_str++);
        int row = *(fen_str++);
        if(!(col >= 'a' && col <= 'h')) return false;
        if(!(row >= '1' && row <= '8')) return false;
        m_has_en_passant = true;
        m_en_passant_column = (col - 'a');
//        cout << "en passant " << (col - 'a') << endl;
    }

    m_material = eval_material();
    Assert(m_material < SCORE::MAX && m_material > SCORE::MIN);

    if(need_reflection){
        reflect_in_place();
    }

    // skip ws
    while(isspace(*(fen_str)))  fen_str++;

    rest_of_string = fen_str;
    
    
    return true;
}

//# BOARD::zobrist_hash() {{{2
/// Compute zobrist hash usin array random_values from CONSTANT_TABLE
bb_t BOARD::zobrist_hash() const 
{
    return zobrist_hash(CONSTANT_TABLE::random_values);
}
//# BOARD::zobrist_hash() {{{2
/// Compute zobrist hash usin array random_values
bb_t BOARD::zobrist_hash(const bb_t random_values[]) const
{
    bb_t res = 0;
    for(int p = K; p <= P; p++){
        BB ally = ally_piece_bb(p);
        while(ally){
            POS pos = ally.pop_first_one();
            res ^= random_values[p*64 + pos];
        }
        BB enemy = enemy_piece_bb(p);
        while(enemy){
            POS pos = enemy.pop_first_one();
            res ^= random_values[(p+6)*64 + pos];
        }
    }       
    if(m_has_en_passant)
        res ^= random_values[12*64+m_en_passant_column];
    res^= random_values[12*64+6+m_castling_info.raw()];
    return res;

}
//# BOARD::reflect_in_place() {{{2
/// Reflect the board -- exchange dark and light sides.
void BOARD::reflect_in_place()
{
    // reflect colors
    BB tmp = m_color_bb[L].reflect();
    m_color_bb[L] = m_color_bb[D].reflect();
    m_color_bb[D] = tmp;

    // reflect pieces 
    m_piece_bb[K] = m_piece_bb[K].reflect();
    m_piece_bb[Q] = m_piece_bb[Q].reflect();
    m_piece_bb[R] = m_piece_bb[R].reflect();
    m_piece_bb[B] = m_piece_bb[B].reflect();
    m_piece_bb[N] = m_piece_bb[N].reflect();
    m_piece_bb[P] = m_piece_bb[P].reflect();
    
    m_is_reflected = !m_is_reflected;

    Assert(m_material < SCORE::MAX && m_material > SCORE::MIN);
    m_material = -m_material;
    
    m_castling_info.reflect();
}

//# BOARD::make_move() {{{2
/** Make the move, update the board.
  At entry `res` must be a copy of `this`.
*/
void BOARD::make_move(BOARD &res, PIECE from_piece, POS from, POS to, PIECE promo) const 
{
    Assert(m_material < SCORE::MAX && m_material > SCORE::MIN);

    PIECE to_piece   = from_piece;
    BB enemy         = enemy_bb();
    AssertBoard(ally_bb()[from]);
    AssertBoard(!ally_bb()[to]);
    if(enemy[to]){
        PIECE captured_piece = get_piece_no_K(to);
        AssertBoard(get_piece(to) != K);
        res.m_color_bb[D].clear(to);
        res.m_piece_bb[captured_piece].clear(to);
        res.m_material += SCORE::piece_score(captured_piece);
    }
    res.m_color_bb[L].clear(from);
    res.m_piece_bb[from_piece].clear(from);
    
    // promotion
    if(from_piece == P && promo != K){
        to_piece = promo; // move.get_promot_piece();
        Assert(to_piece != P);
        res.m_material -= SCORE::SCORE_P;
        res.m_material += SCORE::piece_score(to_piece);
    }

    // castling: move rook
    if(from_piece == K && from == E1){
        if(to == G1){
            Assert(ally_piece_bb(R)[H1]);

            res.m_color_bb[L].clear(H1);
            res.m_piece_bb[R].clear(H1);

            res.m_color_bb[L].set(F1);
            res.m_piece_bb[R].set(F1);
        }else if(to == C1){
            Assert(ally_piece_bb(R)[A1]);

            res.m_color_bb[L].clear(A1);
            res.m_piece_bb[R].clear(A1);

            res.m_color_bb[L].set(D1);
            res.m_piece_bb[R].set(D1);
        }
    }

    // en passant 
    if(        from_piece == P
            && from.row() == ROW_5 
            && !enemy[to]
            && from.col() != to.col() 
            ){
//        cout << "EN PASSANT " << from << " " << to << endl;
        POS capture_pos(to, -1, 0);

        Assert(capture_pos.row() == from.row());
        Assert(enemy_piece_bb(P)[capture_pos]);


        res.m_color_bb[D].clear(capture_pos);
        res.m_piece_bb[P].clear(capture_pos);
        res.m_material += SCORE::SCORE_P;
    }

    res.m_color_bb[L].set(to);
    res.m_piece_bb[to_piece].set(to);

    // if we moved K, mark it in res
    if(from_piece == K){
        res.m_castling_info.clear_L_KQ();
    }

    // if the move is from H1/A1 mark appropriate light rook as moved
    if(from_piece == R){
        if(from == H1){
            res.m_castling_info.clear_L_K();
        }
        if(from == A1){
            res.m_castling_info.clear_L_Q();
        }
    }
    // if the move is to H8/A8 mark appropriate dark rook as moved 
    if(to == H8){
        res.m_castling_info.clear_D_K();
    }else if(to == A8){
        res.m_castling_info.clear_D_Q();
    }

    // en passant
    res.m_has_en_passant = false;
    res.m_en_passant_column = 0;
    if(from_piece == P && from.row() == ROW_2 && to.row() == ROW_4){
        res.m_has_en_passant = true;
        res.m_en_passant_column = to.col();
        Assert(to.col() == from.col());
    }

    Assert(m_material < SCORE::MAX && m_material > SCORE::MIN);
}

//# BOARD::make_move()
void BOARD::make_move(BOARD &res, MOVE move) const
{

    // copy the board
    res = *this;

    POS from = move.from();
    Assert(get_occupied(from));
         if(piece_bb(P)[from]) make_move(res, P, from, move.to(), move.get_promot_piece());
    else if(piece_bb(N)[from]) make_move(res, N, from, move.to(), K);
    else if(piece_bb(B)[from]) make_move(res, B, from, move.to(), K);
    else if(piece_bb(R)[from]) make_move(res, R, from, move.to(), K);
    else if(piece_bb(Q)[from]) make_move(res, Q, from, move.to(), K);
    else                       make_move(res, K, from, move.to(), K);
}

//# BOARD::is_draw_by_material() {{{2
bool BOARD::is_draw_by_material() const
{
    if(piece_bb(Q) | piece_bb(R) | piece_bb(P))
        return false;
    BB BN = piece_bb(B) | piece_bb(N);
    if(BN.popcnt() > 1)
        return false;
    return true;
}


//# BOARD::eval_material() {{{2
/// Evaluate material
SCORE BOARD::eval_material() const
{
    score_t res = SCORE::MED;
    res += (ally_piece_bb(Q).popcnt() - enemy_piece_bb(Q).popcnt()) * SCORE::SCORE_Q;
    res += (ally_piece_bb(R).popcnt() - enemy_piece_bb(R).popcnt()) * SCORE::SCORE_R;
    res += (ally_piece_bb(P).popcnt() - enemy_piece_bb(P).popcnt()) * SCORE::SCORE_P;
    res += (ally_piece_bb(B).popcnt() - enemy_piece_bb(B).popcnt()) * SCORE::SCORE_B;
    res += (ally_piece_bb(N).popcnt() - enemy_piece_bb(N).popcnt()) * SCORE::SCORE_N;
    Assert(res < SCORE::MAX && res > SCORE::MIN);
    return res;
}


//# BOARD::evaluate_pure_pawns() {{{2
score_t BOARD::evaluate_pure_pawns(BB pawns, BB enemy_pawns) const
{
    score_t res = 0;
    const score_t row_bonuses[8] = {0, 0, 1, 2, 4, 24, 64, 0 };

    DEBUG_DECL(const int deb = 0);

    DO_DEBUG(deb, cout 
            << "evaluate_pure_pawns" << endl 
            << pawns << endl << enemy_pawns << endl;);

#define ADD_BONUS(bonus, reason) \
    do{ \
        score_t b = bonus;\
        res += b;\
        DO_DEBUG(deb, cout << "    " << b << "\t: " << (reason) << endl;); \
    }while(0)


    BB occupied_cols(0);


    BB t = pawns;
    while(t){
        POS pos = t.pop_first_one();
        pos_t col = pos.col();
        pos_t row = pos.row();


        DO_DEBUG(deb, cout << "  " << pos << endl;);

        // row bonus
        ADD_BONUS(row_bonuses[row], "row bonus");

        if(0)
        if(occupied_cols[col]){ 
            ADD_BONUS(-20, "two pawns on one col");
        }
        occupied_cols.set(col);

        // take enemy pawns into account
        if(0)
        if((enemy_pawns & TABLE.cols[col]).empty()){
            ADD_BONUS(5, "not blocked by enemy at this col");

            if(((col == COL_A) || (enemy_pawns & TABLE.cols[col - 1]).empty())
            && ((col == COL_H) || (enemy_pawns & TABLE.cols[col + 1]).empty())){
                ADD_BONUS(10, "not blocked by enemy at neibors cols");
            }

        }

        {
            if(col != COL_A){
                //            if(pawns & TABLE.cols[col-1]){
                //                ADD_BONUS(5, "column at left has a friendly pawn");
                if(pawns[POS(pos, -1, -1)]){
                    ADD_BONUS(5, "protected by pawn at left");
                }
                //            }
            }

            if(col != COL_H){
                if(pawns & TABLE.cols[col+1]){
                    ADD_BONUS(5, "column at right has a friendly pawn");
                    if(pawns[POS(pos, -1, +1)]){
                        ADD_BONUS(5, "protected by pawn at right");
                    }
                }
            }
        }
    }
    DO_DEBUG(deb, cout << "\tres = " << res << endl;);
#undef ADD_BONUS
    return res;
}
//# BOARD::evaluate_pawns() {{{2
/// Very basic pawn evaluation. 
/// TODO: more rules, caching 
score_t BOARD::evaluate_pawns() const
{   
    score_t res = 0;
    BB l_pawns = ally_piece_bb(P);
    BB d_pawns = enemy_piece_bb(P);
    res += evaluate_pure_pawns(l_pawns, d_pawns);
    res -= evaluate_pure_pawns(d_pawns.reflect(), l_pawns.reflect());
//    cout << "evaluate_pawns " << res << endl;
    return res;
}

//# BOARD::evaluate_mobility() {{{2
/// TODO: this one is VERY slow
score_t BOARD::evaluate_mobility() const
{   
    score_t res = 0;
    BB t;

    t = ally_piece_bb(Q);
    while(t) res += 4*mobility_count_Q(t.pop_first_one());
    t = enemy_piece_bb(Q);
    while(t) res -= 4*mobility_count_Q(t.pop_first_one());

    t = ally_piece_bb(R);
    while(t) res += 2*mobility_count_R(t.pop_first_one());
    t = enemy_piece_bb(R);
    while(t) res -= 2*mobility_count_R(t.pop_first_one());

    t = ally_piece_bb(B);
    while(t) res += mobility_count_B(t.pop_first_one());
    t = enemy_piece_bb(B);
    while(t) res -= mobility_count_B(t.pop_first_one());


    t = ally_piece_bb(N);
    while(t) res += mobility_count_N(t.pop_first_one());
    t = enemy_piece_bb(N);
    while(t) res -= mobility_count_N(t.pop_first_one());



    return res;

}

//# BOARD::evaluate() {{{2
SCORE BOARD::evaluate(score_t alpha, score_t beta) const
{
    score_t res = get_material();
    Assert(res == eval_material());

    const score_t threshold = SCORE::SCORE_P;
    Assert(alpha < beta);
    if(res < alpha - threshold) return res;
    if(res > beta  + threshold) return res;
 
    res += evaluate_bonus();
    return res;
}

//# BOARD::evaluate_bonus() {{{2
/// Evaluate position except for material. 
/// Very basic implementation. TODO
score_t BOARD::evaluate_bonus() const
{
    score_t res = 0;
    res += evaluate_pawns();
//    res += evaluate_mobility();
    return res;
}
//# BOARD::attackers() {{{2
/**
    Compute the bitboard of dark pieces that attack the square `pos`.
    For all 8 drections of slide movements 
    (r=right, u=up, l=left, d=down, lu=left-up, etc)
    we compute the 'slide' bitboard. 
    If such slide is empty, no attackers in this direction.
    If the slide is not empty, the attacker is located at 
    slide.first_one() or slide.last_one(). 


Example: 
Board: We need to compute attackers of light King. 
@verbatim
    b . . . . . . .
    . q . . n . . .
    . . . . . . . .
    . r . K . . r .
    . . . . . . . .
    . . . P . . . .
    . . . . . . . .

        Slide r             Slide u             Slide l             Slide d     
    . . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . . 
    . . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . . 
    . . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . . 
    . . . . . . X .     . . . . . . . .     . X . . . . . .     . . . . . . . . 
    . . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . . 
    . . . . . . . .     . . . . . . . .     . . . . . . . .     . . . X . . . . 
    . . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . . 
       
        Slide ru            Slide lu            Slide rd            Slide ld     
    . . . . . . . .     X . . . . . . .     . . . . . . . .     . . . . . . . .
    . . . . . . . .     . X . . . . . .     . . . . . . . .     . . . . . . . .
    . . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
    . . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
    . . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
    . . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
    . . . . . . . .     . . . . . . . .     . . . . . . . .     . . . . . . . .
@endverbatim

    For slide r the possible R/Q atacker is in slide_r.first_one();
    For slide l the possible R/Q atacker is in slide_l.last_one();
    For slide d the possible R/Q atacker is in slide_l.last_one();
    For slide lu the possible B/Q atacker is in slide_lu.first_one();

    Now we intersect Q/R bitboards with Q/R attackers and Q/B bitboards with Q/B attackers.

    So, the bitboards are: 
@verbatim
    for Q/R atackers    for Q/B attackers  
    . . . . . . . .     . . . . . . . .    
    . . . . . . . .     . X . . . . . .    
    . . . . . . . .     . . . . . . . .    
    . X . . . . X .     . . . . . . . .     
    . . . . . . . .     . . . . . . . .    
    . . . . . . . .     . . . . . . . .    
    . . . . . . . .     . . . . . . . .    
@endverbatim    
    
    Final step, union of Q/R and Q/B atatckers, as well as K,N,P
@verbatim
    all atackers    
    . . . . . . . . 
    . X . . X . . . 
    . . . . . . . . 
    . X . . . . X . 
    . . . . . . . . 
    . . . . . . . . 
    . . . . . . . . 
@endverbatim    


 */
BB BOARD::attackers(POS pos) const
{

    BB occupied = occupied_bb();
    // Sliding pieces: R & Q -----------------------------------------
    BB rq_border = 0;
    // r
    BB slide_r = TABLE.slide[pos].r & occupied;
    if(slide_r){
        pos_t p_r = slide_r.first_one();
        rq_border.set(p_r);
    }
    
    // u
    BB slide_u = TABLE.slide[pos].u & occupied;
    if(slide_u){
        pos_t p_u = slide_u.first_one();
        rq_border.set(p_u);
    }
    
    // l
    BB slide_l = TABLE.slide[pos].l & occupied;
    if(slide_l){
        pos_t p_l = slide_l.last_one();
        rq_border.set(p_l);
    }
    
    // d
    BB slide_d = TABLE.slide[pos].d & occupied;
    if(slide_d){
        pos_t p_d = slide_d.last_one();
        rq_border.set(p_d);
    }

    BB piece_Q = piece_bb(Q);
    rq_border &= piece_Q | piece_bb(R);

    BB res = rq_border;

    // Sliding pieces: B & Q -----------------------------------------
    BB bq_border = 0;
    // ru
    BB slide_ru = TABLE.slide[pos].ru & occupied;
    if(slide_ru){
        pos_t p_ru = slide_ru.first_one();
        bq_border.set(p_ru);
    }

    // lu   
    BB slide_lu = TABLE.slide[pos].lu & occupied;
    if(slide_lu){
        pos_t p_lu = slide_lu.first_one();
        bq_border.set(p_lu);
    }
    
    // rd   
    BB slide_rd = TABLE.slide[pos].rd & occupied;
    if(slide_rd){
        pos_t p_rd = slide_rd.last_one();
        bq_border.set(p_rd);
    }

    // ld
    BB slide_ld = TABLE.slide[pos].ld & occupied;
    if(slide_ld){
        pos_t p_ld = slide_ld.last_one();
        bq_border.set(p_ld);
    }
    
    bq_border &= piece_Q | piece_bb(B);

    res |= bq_border;

    // Non-sliding pieces:  K, N, P
    res |= (piece_bb(K) & TABLE.K_attacks[pos])
        |  (piece_bb(N) & TABLE.N_attacks[pos])
    ;

    return res;
}

BB BOARD::enemy_attackers(POS pos) const
{
    return (attackers(pos) | (piece_bb(P) & TABLE.D_P_attacks[pos])) & enemy_bb();
}
BB BOARD::ally_attackers(POS pos)  const
{
    return (attackers(pos) | (piece_bb(P) & TABLE.L_P_attacks[pos])) & ally_bb();
}

//# BOARD::mobility_R() {{{2
/**
    Compute the bitboard of possible rook movements from suqare 'pos'. 

@verbatim
    A=ally, E=enemy, R=rook to move.        Must get: 
    . . . . . . . .                      . . . . . . . .    
    . . . . A . . .                      . . . . . . . .    
    . . . . . . . .                      . . . . X . . .    
    . . . . R E . .                      X X X X . X . .     
    . . . . . . . .                      . . . . X . . .    
    . . . . . . . .                      . . . . X . . .    
    . . . . E . . .                      . . . . X . . .    
@endverbatim    

See http://www.cis.uab.edu/hyatt/bitmaps.html, section 2

*/

BB BOARD::mobility_R(POS pos) const
{
    BB occupied = occupied_bb();
    BB ally     = ally_bb();


    // slides from the table
    BB t_r = TABLE.slide[pos].r;
    BB t_l = TABLE.slide[pos].l;
    BB t_u = TABLE.slide[pos].u;
    BB t_d = TABLE.slide[pos].d;
    
    // slides intersected with occupied
    BB slide_r = (t_r & occupied);
    BB slide_l = (t_l & occupied);
    BB slide_u = (t_u & occupied);
    BB slide_d = (t_d & occupied);

    // set corners 
//    pos_t row = pos.row();
//    pos_t col = pos.col();
//    slide_r.set(POS(row, COL_H));
//    slide_l.set(POS(row, COL_A));
//    slide_u.set(POS(ROW_8, col));
//    slide_d.set(POS(ROW_1, col));
//
    if(slide_r) t_r = t_r ^ TABLE.slide[slide_r.first_one()].r;
    if(slide_l) t_l = t_l ^ TABLE.slide[slide_l.last_one()].l;
    if(slide_u) t_u = t_u ^ TABLE.slide[slide_u.first_one()].u;
    if(slide_d) t_d = t_d ^ TABLE.slide[slide_d.last_one()].d;
    
    BB all_moves = t_r | t_l | t_u | t_d;

//    BB all_moves = t_r ^ TABLE.slide[slide_r.first_one()].r
//                 | t_l ^ TABLE.slide[slide_l.last_one()].l
//                 | t_u ^ TABLE.slide[slide_u.first_one()].u
//                 | t_d ^ TABLE.slide[slide_d.last_one()].d;
                 
    /*
    pos_t border;

    // compute distances from 'pos' to borders r/l/u/d
    border = slide_r.first_one();
    pos_off_t off_r = border - pos;

    border = slide_l.last_one();
    pos_off_t off_l = pos - border;

    border = slide_u.first_one();
    pos_off_t off_u = (border - pos) >> 3;

    border = slide_d.last_one();
    pos_off_t off_d = (pos - border) >> 3;

    // intersect waves of appropriate lengths with slides
    BB all_moves 
        = ((TABLE.wave[pos][off_r] & t_r)
        | ( TABLE.wave[pos][off_l] & t_l))
        | ((TABLE.wave[pos][off_u] & t_u)
        | ( TABLE.wave[pos][off_d] & t_d))
        ;
    */
    // we can not eat allys
    all_moves &= ~ally;

    // done
    return all_moves;
}

//# BOARD::mobility_B() {{{2
/**
    Compute the bitboard of possible bishop movements from suqare 'pos'. 

@verbatim
    A=ally, E=enemy, R=rook to move.        Must get: 
    . . . . . . . .                      . . . . . . . .    
    . . A . . . . .                      . . . . . . . .    
    . . . . . E . .                      . . . X . X . .    
    . . . . B . . .                      . . . . . . . .     
    . . . . . . . .                      . . . X . X . .    
    . . . . . . . .                      . . X . . . X .    
    . E . . . . . .                      . X . . . . . X    
@endverbatim    

    The code here is slightly different from the code in BOARD::mobility_R(),
    but the edea is the same. 

    I have not observed signficant differences in performance of
    BOARD::mobility_R() and BOARD::mobility_B().
*/

BB BOARD::mobility_B(POS pos) const
{
    BB occupied = occupied_bb();
    BB ally     = ally_bb();

    BB wave_ru(0);
    BB wave_rd(0);
    BB wave_lu(0);
    BB wave_ld(0);

    // slides from table
    BB t_ru = TABLE.slide[pos].ru;
    BB t_rd = TABLE.slide[pos].rd;
    BB t_lu = TABLE.slide[pos].lu;
    BB t_ld = TABLE.slide[pos].ld;

    // interesct slides with occupied
    BB slide_ru = t_ru & occupied;
    BB slide_rd = t_rd & occupied;
    BB slide_lu = t_lu & occupied;
    BB slide_ld = t_ld & occupied;

    if(slide_ru) t_ru = t_ru ^ TABLE.slide[slide_ru.first_one()].ru;
    if(slide_rd) t_rd = t_rd ^ TABLE.slide[slide_rd.last_one()].rd;
    if(slide_lu) t_lu = t_lu ^ TABLE.slide[slide_lu.first_one()].lu;
    if(slide_ld) t_ld = t_ld ^ TABLE.slide[slide_ld.last_one()].ld;

    BB all_moves = (t_ru | t_rd | t_lu | t_ld) & ~ally;

    /*
    if(slide_ru){
        // if the slide is not empty, compute the distance from nearest piece, 
        // intersect with wave of appropriate distance 
        pos_t border = slide_ru.first_one();
        pos_off_t off = (border - pos) >> 3;
        wave_ru = TABLE.wave[pos][off-0] & t_ru;
    }else{
        // slide is empty -- go untill the end
        wave_ru = t_ru;
    }
    
    if(slide_rd){
        pos_t border = slide_rd.last_one();
        pos_off_t off = (pos - border + 7) >> 3;
        wave_rd = TABLE.wave[pos][off-0] & t_rd;
    }else{
        wave_rd = t_rd;
    }
    if(slide_lu){
        pos_t border = slide_lu.first_one();
        pos_off_t off = (border - pos + 7) >> 3;
        wave_lu = TABLE.wave[pos][off-0] & t_lu;
    }else{
        wave_lu = t_lu;
    }

    if(slide_ld){
        pos_t border = slide_ld.last_one();
        pos_off_t off = (pos - border) >> 3;
        wave_ld = TABLE.wave[pos][off-0] & t_ld;
    }else{
        wave_ld = t_ld;
    }

    BB all_moves = (wave_ru | wave_rd | wave_lu | wave_ld) & ~ally;
    */
    return all_moves;
}
//# BOARD::mobility_count_R() {{{2
// TODO 
int64_t BOARD::mobility_count_R(POS pos) const
{
    BB occupied = occupied_bb();
    BB ally     = ally_bb();


    // slides from the table
    BB t_r = TABLE.slide[pos].r;
    BB t_l = TABLE.slide[pos].l;
    BB t_u = TABLE.slide[pos].u;
    BB t_d = TABLE.slide[pos].d;
    
    // slides intersected with occupied
    BB slide_r = (t_r & occupied);
    BB slide_l = (t_l & occupied);
    BB slide_u = (t_u & occupied);
    BB slide_d = (t_d & occupied);

    // set corners 
    pos_t row = pos.row();
    pos_t col = pos.col();
    slide_r.set(POS(row, COL_H));
    slide_l.set(POS(row, COL_A));
    slide_u.set(POS(ROW_8, col));
    slide_d.set(POS(ROW_1, col));

    pos_t border;

    // compute distances from 'pos' to borders r/l/u/d
    border = slide_r.first_one();
    pos_off_t off_r = border - pos;

    border = slide_l.last_one();
    pos_off_t off_l = pos - border;

    border = slide_u.first_one();
    pos_off_t off_u = (border - pos) >> 3;

    border = slide_d.last_one();
    pos_off_t off_d = (pos - border) >> 3;

    return off_r + off_l + off_u + off_d;
}

//# BOARD::mobility_count_B() {{{2
// TODO 
int64_t BOARD::mobility_count_B(POS pos) const
{
    BB occupied = occupied_bb();
    BB ally     = ally_bb();

    BB wave_ru(0);
    BB wave_rd(0);
    BB wave_lu(0);
    BB wave_ld(0);

    // slides from table
    BB t_ru = TABLE.slide[pos].ru;
    BB t_rd = TABLE.slide[pos].rd;
    BB t_lu = TABLE.slide[pos].lu;
    BB t_ld = TABLE.slide[pos].ld;

    // interesct slides with occupied
    BB slide_ru = t_ru & occupied;
    BB slide_rd = t_rd & occupied;
    BB slide_lu = t_lu & occupied;
    BB slide_ld = t_ld & occupied;

    // set corners 
    pos_t row = pos.row();
    pos_t col = pos.col();
    pos_t b_off;

    b_off = min(COL_H - col, ROW_8 - row);
    slide_ru.set(POS(row+b_off, col+b_off));
    b_off = min(COL_H - col, row - ROW_1);
    slide_rd.set(POS(row-b_off, col+b_off));
    b_off = min(col - COL_A, ROW_8 - row);
    slide_lu.set(POS(row+b_off, col-b_off));
    b_off = min(col - COL_A, row - ROW_1);
    slide_ld.set(POS(row-b_off, col-b_off));


    pos_off_t off_ru = (slide_ru.first_one() - pos) >> 3;
    pos_off_t off_rd = (pos - slide_rd.last_one() + 7) >> 3;
    pos_off_t off_lu = (slide_lu.first_one() - pos + 7) >> 3;
    pos_off_t off_ld = (pos - slide_ld.last_one()) >> 3;

    return off_ru + off_rd + off_lu + off_ld;
}
//# BOARD::mobility_Q() {{{2
/// Compute mobility BB for Queen
BB BOARD::mobility_Q(POS pos) const
{
    return mobility_B(pos) | mobility_R(pos);
}

//# BOARD::mobility_count_Q() {{{2
/// Compute mobility count for Queen
int64_t BOARD::mobility_count_Q(POS pos) const
{
    return mobility_count_B(pos) + mobility_count_R(pos);
}

//# BOARD::mobility_N() {{{2
/// Compute mobility BB for Knight
BB BOARD::mobility_N(POS pos) const
{   
    return TABLE.N_attacks[pos] & (~ally_bb());
}

//# BOARD::mobility_count_N() {{{2
/// Compute mobility count for Knight
int64_t BOARD::mobility_count_N(POS pos) const
{   
    return TABLE.N_attacks_count[pos];
}


//# BOARD::gen_castling() {{{2
/// Bitboard of King moves (only castling) 
BB BOARD::gen_castling() const
{
    BB kings = ally_piece_bb(K);
    BB occupied = occupied_bb();
    POS pos = kings.first_one();
    BB res(0);
    // at least one of rooks never moved
    if(!m_castling_info.L_KQ())
        return res;
    AssertBoard(pos == POS(E1));
    
    // K is not attacked
    if(enemy_attackers(pos)) // E1
        return res;

    if(m_castling_info.L_K()){
        AssertBoard(ally_piece_bb(R)[H1]);
    }
    if(m_castling_info.L_Q()){
        AssertBoard(ally_piece_bb(R)[A1]);
    }
    
    // try to castle king rook
    if(m_castling_info.L_K()
            && !occupied[F1]
            && !occupied[G1]
            && !enemy_attackers(F1)
            ){
        res.set(G1);
    }
    
    // try to castle queen rook
    if(m_castling_info.L_Q()
            && !occupied[D1]
            && !occupied[C1]
            && !occupied[B1]
            && !enemy_attackers(D1)
            ){
        res.set(C1);
    }
    return res;
}

//# BOARD::mobility_K() {{{2
/// Bitboard of King moves (w/o castling) 
BB BOARD::mobility_K(POS pos) const
{   
    return (TABLE.K_attacks[pos] & (~ally_bb())) | gen_castling();
}

//# BOARD::mobility_P() {{{2
/// Bitboard of light pawn moves (w/o en passant)
BB BOARD::mobility_P(POS pos) const
{
    BB occupied      = occupied_bb();
    BB enemy         = enemy_bb();

    BB res = (TABLE.D_P_attacks[pos] & enemy) | (TABLE.L_P_moves[pos] & ~occupied);
    if(pos.row() == ROW_2 && occupied[POS(pos, 1, 0)])
        res.clear(POS(pos, 2, 0));
    return res;
}

//# BOARD::is_legal_move() {{{2
bool BOARD::is_legal_move(MOVE move) const
{
    if(is_pseudo_move(move)){
        BOARD moved_board(*this, move);
        if(!moved_board.ally_K_is_attacked())
            return true;
    }
    return false;
}
//# BOARD::is_pseudo_move() {{{2
/// TODO: does not handle en passant
bool BOARD::is_pseudo_move(MOVE move) const
{
    if(move.is_illegal())
        return false;

    BB ally = ally_bb();

    POS from_pos = move.from();
    // from_pos must be occupied by an ally
    if(!ally[from_pos])
        return false;
    PIECE from_piece = get_piece(from_pos);
    POS to_pos   = move.to();

    switch(from_piece){
        case N: if(mobility_N(from_pos)[to_pos]) return true; break;
        case K: if(mobility_K(from_pos)[to_pos]) return true; break;
        case R: if(mobility_R(from_pos)[to_pos]) return true; break;
        case B: if(mobility_B(from_pos)[to_pos]) return true; break;
        case Q: if(mobility_Q(from_pos)[to_pos]) return true; break;
        case P: if(mobility_P(from_pos)[to_pos]) return true; break;
        default: 
            return false;
    }
    return false;
}
//# BOARD::gen_moves() {{{2
/**
    Geneate all pseudo moves for this board. 
    For each generated pseudo move action() is called. 
    See also GEN_MOVE_ACTION_STORE 
*/
template <class GEN_MOVE_ACTION>
size_t BOARD::gen_moves(GEN_MOVE_ACTION &action) const
{
    // {{{3
    Assert(m_material < SCORE::MAX && m_material > SCORE::MIN);

    size_t res = 0;

    BB  piece = ally_piece_bb(K);
    Assert(piece);
    Assert(piece.popcnt() == 1);
    POS K_pos = piece.first_one();



    BB  moves;
    POS pos(A1), new_pos(A1);
    // N {{{3
    piece = ally_piece_bb(N);
    while(piece){
        pos = piece.pop_first_one();
        moves = mobility_N(pos);
        moves = action.mask_target(moves);
        while(moves){
            new_pos = moves.pop_first_one();
            if(action(*this, res++, pos, new_pos, K, N, K_pos)) return res;
        }
    }

    // K {{{3
    moves = mobility_K(K_pos);
    moves = action.mask_target(moves);
    while(moves){
        new_pos = moves.pop_first_one();
        if(action(*this, res++, K_pos, new_pos, K, K, new_pos)) return res;
    }
    
    // B {{{3
    piece = ally_piece_bb(B);
    while(piece){
        pos = piece.pop_first_one();
        moves = mobility_B(pos);
        moves = action.mask_target(moves);
        while(moves){
            new_pos = moves.pop_first_one();
            if(action(*this, res++, pos, new_pos, K, B, K_pos)) return res;
        }
    }

    // R {{{3
    piece = ally_piece_bb(R);
    while(piece){
        pos = piece.pop_first_one();
        moves = mobility_R(pos);
        moves = action.mask_target(moves);
        while(moves){
            new_pos = moves.pop_first_one();
            if(action(*this, res++, pos, new_pos, K, R, K_pos)) return res;
        }
    }

    // Q {{{3
    piece = ally_piece_bb(Q);
    while(piece){
        pos = piece.pop_first_one();
        moves = mobility_Q(pos);
        moves = action.mask_target(moves);
        while(moves){
            new_pos = moves.pop_first_one();
            if(action(*this, res++, pos, new_pos, K, Q, K_pos)) return res;
        }
    }

    // P {{{3
    BB pawns = ally_piece_bb(P);
    piece = pawns & TABLE.rows_23456;
    while(piece){
        pos = piece.pop_first_one();
        moves = mobility_P(pos);
        moves = action.mask_target(moves);
        while(moves){
            new_pos = moves.pop_first_one();
            if(action(*this, res++, pos, new_pos, K, P, K_pos)) return res;
        }
    }
    // P promotions {{{3
    piece = pawns & TABLE.row_7;
    if(action.allow_promo()){
        while(piece){
            pos = piece.pop_first_one();
            moves = mobility_P(pos);
            // no masking 
            while(moves){
                new_pos = moves.pop_first_one();
                if(action(*this, res++, pos, new_pos, Q, P, K_pos)) return res;
                if(action(*this, res++, pos, new_pos, R, P, K_pos)) return res;
                if(action(*this, res++, pos, new_pos, B, P, K_pos)) return res;
                if(action(*this, res++, pos, new_pos, N, P, K_pos)) return res;
            }
        }
    }
    // handle en passant {{{3
    if(action.allow_en_passant() && m_has_en_passant){
        pos_t en_passant_col = m_en_passant_column;
        
        POS en_passant_pos(ROW_5, en_passant_col);

        Assert(enemy_piece_bb(P)[en_passant_pos]);
        if(en_passant_col < COL_H){
            POS ally_pos    = POS(en_passant_pos, 0, 1);
            if(pawns[ally_pos]){
                POS capture_pos = POS(en_passant_pos, 1, 0);
                AssertBoard(!occupied_bb()[capture_pos]);
                if(action(*this, res++, ally_pos, capture_pos, K, P, K_pos)) return res;
            }
        }

        if(en_passant_col > COL_A){
            POS ally_pos    = POS(en_passant_pos, 0, -1);
            if(pawns[ally_pos]){
                POS capture_pos = POS(en_passant_pos, 1, 0);
                AssertBoard(!occupied_bb()[capture_pos]);
                if(action(*this, res++, ally_pos, capture_pos, K, P, K_pos)) return res;
            }
        }
    }

    // end {{{3
    return res;
}

//# BOARD::set_piece() {{{2
void BOARD::set_piece(POS pos, PIECE piece, COLOR color)
{
    m_piece_bb[piece].set(pos);
    m_color_bb[color].set(pos);
}

//# BOARD::piece_to_char() {{{2
int  BOARD::piece_to_char(PIECE piece, COLOR color)
{
    int res = 0;
    switch(piece){
        case K: res = 'K'; break;
        case Q: res = 'Q'; break;
        case R: res = 'R'; break;
        case B: res = 'B'; break;
        case N: res = 'N'; break;
        case P: res = 'P'; break;
        default: Assert(0); break;
    }
    if(color == D)
        res = res - 'A' + 'a';
    return res;
}

//# BOARD::char_to_piece() {{{2
int BOARD::char_to_piece(int c)
{
    switch(c){
        case 'k': case 'K': return K;
        case 'q': case 'Q': return Q;
        case 'r': case 'R': return R;
        case 'b': case 'B': return B;
        case 'n': case 'N': return N;
        case 'p': case 'P': return P;
        default: return PIECE_ERROR;
    }
}
//# BOARD::char_to_color() {{{2
COLOR BOARD::char_to_color(int c)
{
    if(c >= 'A' && c <= 'Z') return L;
    else                     return D;
}

//# class STATISTICS {{{1
class STATISTICS{
    uint64_t search_count[MAX_PLY];
    uint64_t ab_cut[MAX_N_MOVES];
public: 
    STATISTICS() {flush();}
    void flush(){
        memset(this, 0, sizeof(*this));
    }
    ostream & show(ostream &os){
        os << "search: " 
            << (tot_search() / 1000000) << " " 
           // (search_count[1] / 1000000)  << " " 
//            << (tot_search() - search_count[1]) << " "
            << "avg_cut: " << avg_ab_cut();
        return os;
    }

    void increment_search(size_t ply, int incr = 1){
        search_count[ply] += incr;
    }

    size_t tot_search(){
        size_t res = 0;
        for(size_t i = 0; i < MAX_PLY; i++)
            res += search_count[i];
        return res;
    }

    void increment_ab_cut(size_t i){
        ab_cut[i]++;
    }

    double avg_ab_cut(){
        size_t tot = 0, res = 0;
        for(size_t i = 0; i < MAX_N_MOVES; i++){
            tot += ab_cut[i];
            res += (i) * ab_cut[i];
        }
        return (double) res / tot;
            
    }
};

//# TT (transposition table) {{{1

//# class TTE (transposition table entry) {{{2
class TTE{
    BB m_lock;
    BB m_b1;

    bb_t    pack_score(score_t score) const { return score - SCORE::MIN; }
    score_t unpack_score(bb_t  b)     const { return score_t(b) + SCORE::MIN; }
public:
    enum TYPE{
        EXACT,
        ALPHA,
        BETA
    };
    TTE(){}

    TTE (bb_t lock, score_t score, TYPE type, int depth, MOVE::move_t move)
        :m_lock(lock)
        ,m_b1(0)
    {
        Assert(depth >= 0 && depth < (1 << 15));
        Assert(pack_score(score) >= 0 && pack_score(score) < (1<<15));
        Assert(move >= 0 && move < (1 << 15));

        m_b1.put(0, 15, pack_score(score));
        m_b1.put(15, 15, depth);
        m_b1.put(30, 2, type);
        m_b1.put(32, 15, move);

        Assert(score   == get_score());
        Assert(depth   == get_depth());
        Assert(type    == get_type());
        Assert(move    == get_move());
        Assert(lock    == get_lock());
    }

    bb_t         get_lock()     const    {return m_lock;}   
    score_t      get_score()    const    {return unpack_score(m_b1.get(0, 15));}
    int          get_depth()    const    {return m_b1.get(15, 15);}
    TYPE         get_type()     const    {return (TYPE)m_b1.get(30,2);}
    MOVE::move_t get_move()     const    {return m_b1.get(32,15);}

    void clear() {m_b1.clear(); m_lock.clear();}
};

ostream &operator << (ostream &os, TTE tte){
    os << "TTE(" 
        << tte.get_depth() << ","
        << SCORE(tte.get_score()) << ")";
    return os;
}

//# class TT {{{2
/// Transposition Table
class TT{
    TTE *m_tte;
    size_t m_n_bits;
    size_t size()const {return 1ULL << m_n_bits;};
    size_t mask()const {return size() - 1;};
public:
    TT(size_t n_bits)
        :m_tte(NULL)
    {
        resize(n_bits);
    }

    void reset()
    {
        memset(m_tte, 0, sizeof(TTE) * size());
    }

    void resize(size_t n_bits)
    {
        delete [] m_tte;
        m_n_bits = n_bits;
        m_tte  = new TTE[size()];
        reset();
    }
    
    

    TTE  get(bb_t zobrist_key) {return   m_tte[zobrist_key & mask()];}
    void put(bb_t zobrist_key, TTE tte) {m_tte[zobrist_key & mask()] = tte;}

    TTE  get(const BOARD &board){
        BB zobrist = board.zobrist_hash();
        bb_t zobrist1 = zobrist.get(0, 32);
        bb_t zobrist2 = zobrist.get(32,32);
        TTE tte = get(zobrist1);
        if(tte.get_lock() == zobrist2)
            return tte;
        tte.clear();
        return tte;
    }

    void print_stat(ostream &os){
        map<int, int> m;
        for(size_t i = 0; i < size(); i++){
            m[m_tte[i].get_depth()]++;
        }
        os << "TT: ";
        for(map<int, int>::iterator it = m.begin(); it != m.end(); ++it){
            os << it->first << "=>" << it->second << "  ";
        }
        os << endl;

    }
};

/// The global object 
static TT THE_TT(16);

//# KILLER_HEURISTIC {{{1
/// The killer move heuristic, see http://en.wikipedia.org/wiki/Killer_heuristic
class KILLER_HEURISTIC{
    struct KILLER_FOR_PLY{
        MOVE::move_t killers[3];
    };


    KILLER_FOR_PLY arr[MAX_PLY];
public:
    /// Tell that this move made a cut
    void add_move(MOVE::move_t move, int ply){
        Assert(ply < MAX_PLY);
        KILLER_FOR_PLY &k = arr[ply];
        if(move != k.killers[0]){
//            k.killers[2] = k.killers[1];
            k.killers[1] = k.killers[0];
            k.killers[0] = move;
        }
    }
    /// Return the n-th killer move for the given depth 
    MOVE::move_t killer(int ply, int n = 0){
        KILLER_FOR_PLY &k = arr[ply];
        return k.killers[n];
    }

    int n_killers(int ply){
        return 2;
    }

    bool is_killer(int ply, MOVE::move_t move){
        KILLER_FOR_PLY &k = arr[ply];
        return k.killers[0] == move
            || k.killers[1] == move
//            || k.killers[2] == move
            ;
    }

    /// reset the table
    void reset(){
        memset(this, 0, sizeof(*this));
    }

    KILLER_HEURISTIC(){
        reset();
    }

};



//# I/O {{{1
static string read_line(istream &in)
{
    const int MAX_STRING_LEN = 1024;
    char buff[MAX_STRING_LEN];
    if(!in.good() || in.eof())
        return string("");
    in.getline(buff, MAX_STRING_LEN-1);
    return string(buff);
}


static void read_string_vector(vector<string> &res, istream &in)
{
    while(in.good() && !in.eof()){
        string line(read_line(in));
        if(line.size() > 0)
            res.push_back(line);
    }
}

//# PGN_READER {{{1
/// Read PGN file (http://en.wikipedia.org/wiki/Pgn)
class PGN_READER{
    istream &in;
    bool read_tag();
    bool read_tag_pairs();
    bool read_move_text();
    bool read_move(int expected_num);
    void skip_ws();
    void skip_dollar();
    void skip_comment();

    BOARD  m_board;
    vector<MOVE> m_moves;
    int m_result; // -1 for loss, 0 for draw, 1 for win
public:
    PGN_READER(istream &in_arg) : in(in_arg){};
    bool read_one_game();
    bool skip_corrupted_game();
    size_t n_moves() const {return m_moves.size();}
    MOVE   move(size_t i) {assert(i < n_moves()); return m_moves[i];}
    int    result()       {return m_result;}
};

//# PGN_READER::skip_ws() {{{2
void PGN_READER::skip_ws()
{
    while(isspace(in.peek()))
        in.ignore();
}
//# PGN_READER::skip_corrupted_game() {{{2
bool PGN_READER::skip_corrupted_game()
{
   if(!in.good() || in.eof())
       return false;
   while(in.peek() != '[' && !in.eof())
       in.ignore();
   if(!in.good() || in.eof())
       return false;
   return true;
}
//# PGN_READER::skip_comment() {{{2
void PGN_READER::skip_comment()
{
    if(in.peek() != '(' && in.peek() != '{')
        return;
    while(in.peek() != ')' && in.peek() != '}')
        in.ignore();
    in.ignore();
    return;
}
//# PGN_READER::skip_dollar() {{{2
void PGN_READER::skip_dollar()
{
    skip_ws();
    if(in.peek() != '$')
        return;
    in.ignore();
    int num;
    in >> num;
    return;
}
//# PGN_READER::read_tag() {{{2
bool PGN_READER::read_tag()
{
    skip_ws();
    // read [
    if(in.peek() != '[')
        return false;
    in.ignore();
    // read TAG
    string tagname;
    in >> tagname;
    // skip WS
    skip_ws();
    // read "name"
    if(in.peek() != '"')
        return false;
    in.ignore();

    string name;
    while(in.good() && !in.eof()){
        if(in.peek() == '\\'){
            in.ignore();
            name += (char)in.get();
        }else if(in.peek() != '"'){
            name += (char)in.get();
        }else{
            break;
        }
    }
    if(in.peek() != '"')
        return false;
    in.ignore();
    // read ']'
    if(in.peek() != ']')
        return false;
    in.ignore();

    if(tagname == "Result"){
        if     (name == "1-0") m_result = 1;
        else if(name == "0-1") m_result = -1;
        else if(name == "1/2-1/2") m_result = 0;
        else                       m_result = 0;
    }

//    cout << tagname << "\t" << name << endl;
    return true;
}
//# PGN_READER::read_tag_pairs() {{{2
bool PGN_READER::read_tag_pairs()
{
    int n_tags = 0;
    while(read_tag())
        n_tags++;
    return n_tags > 0;
}
//# PGN_READER::read_move() {{{2
bool PGN_READER::read_move(int expected_num)
{
    if(!isdigit(in.peek()))
        return false;
    int num = 0;
    in >> num;
    if(num != expected_num)
        return false;
    if(in.peek() != '.')
        return false;
    in.ignore();
    skip_ws();

    string move[3];
    in >> move[0];
    skip_dollar();
    skip_comment();
    in >> move[1];
    skip_dollar();
    skip_comment();

    skip_ws();

    int peek = in.peek();
    if(peek == '0' || peek == '1'){
        in.ignore();
        if(in.peek() == '-' || in.peek() == '/'){
            in.putback(peek);
            in >> move[2];
        }else{
            in.putback(peek);
        }   
    }else if(peek == '*'){
        move[2] = string("*");
        in.ignore();
    }

//    cout << num << ". " << move[0] << " " << move[1] << " " << move[2] << endl;

    for(int i = 0; i < 2; i++){
        string s = move[i];
        MOVE m = m_board.parse_SAN(s);
        if(m.is_illegal())
            if(s == "*" || s == "1-0" || s == "0-1" || s == "1/2-1/2")
                return true;
//        cout << "MOVE[" << i << "]: " << m << endl; 
        if(m.is_illegal())
            return false;
        m_moves.push_back(m);
        m_board.make_move_in_place(m);
        m_board.reflect_in_place();
    }

    return true;
}
//# PGN_READER::read_move_text() {{{2
bool PGN_READER::read_move_text()
{
    int n_moves = 0;
    while(read_move(n_moves + 1))
        n_moves++;
    return n_moves++;
}
//# PGN_READER::read_one_game() {{{2
bool PGN_READER::read_one_game()
{
    skip_ws();
    if(!in.good() || in.eof())
        return false;
    if(!read_tag_pairs()){
        cerr << "corrupted TAGs" << endl;
        return false;
    }
    m_board.set_new_game();
    m_moves.clear();

    if(!read_move_text()){
        cerr << "corrupted MOVEs" << endl;
        return false;
    }
    cout << m_moves.size() << endl << m_board << endl;
    return true;
}

//# OGDB {{{1

/// Statistics for one move
struct POS_STAT
{
    int wins, losses, draws;
    MOVE move;
    POS_STAT() : wins(0), losses(0), draws(0), move(0){} 
    int total() const {return wins + losses + draws;}
    int percent_wins() const {
        double res = wins;
        res /= wins + losses; 
        res *= 100.;
        return (int)res;
    }

    bool operator < (const POS_STAT &p) const {
        return total() > p.total();
    }
};

/// HASH type for hash_map
struct BOARD_HASH
{
    bb_t operator () (const BOARD &b) const{
        return b.zobrist_hash();
    }
};
struct BB_HASH
{
    bb_t operator () (bb_t b) const{
        return b;
    }
};


typedef map<MOVE, POS_STAT>          MOVE_STAT_MAP;
typedef hash_map<BOARD, MOVE_STAT_MAP, BOARD_HASH>   BOARD_STAT_MAP;
typedef hash_set<BOARD, BOARD_HASH> BOARD_SET;

/**
  Generate OGDB file from a file in PGN format 
  */
static void generate_opening_db(
        const string &pgn_path, 
        const string &ogdb_path, 
        size_t max_depth)
{
    BOARD_STAT_MAP pos_stat;
    ifstream in(pgn_path.c_str());
    ofstream out(ogdb_path.c_str());
    assert(in.good() && out.good());

    hash_map<bb_t, BOARD, BB_HASH> zob_board_map;
    
    PGN_READER reader(in);
    int i = 0;
    while(reader.read_one_game() || reader.skip_corrupted_game()){
        i++;
        BOARD board;
        board.set_new_game();
        size_t n = reader.n_moves();
        int result = reader.result();
        for(size_t j = 0; j < min(n,max_depth); j++){
            MOVE move = reader.move(j);
            BOARD t_board = board;
            t_board.clear_reflected();
            POS_STAT &stat = pos_stat[t_board][move];
            stat.wins   += result == 1;
            stat.losses += result == -1;
            stat.draws  += result == 0;
            stat.move    = move;
            board.make_move_in_place(move);
            board.reflect_in_place();
            result = -result;

#if 0
            bb_t zob = t_board.zobrist_hash();
            if(zob_board_map.find(zob) != zob_board_map.end()
                    && !(t_board == zob_board_map[zob])){
                cerr << "ZOB: " << zob << endl;
                cerr << t_board.fen() << endl;
                cerr << zob_board_map[zob].fen() << endl;
            }
            zob_board_map[zob] = t_board;
#endif 
            
        }
        if((i % 5000) == 0){
            cerr << "read :" << i << "\t";;
            cerr 
                << "hash size: " << pos_stat.size() 
                << endl;
        }
    }
    cerr << "read :" << i << "\t";;
    cerr << "HASH size: " << pos_stat.size() << endl;

    hash_map<bb_t, int, BB_HASH> hash_count_map;

    int64_t total_printed = 0;


    for(BOARD_STAT_MAP::iterator it = pos_stat.begin(); 
            it != pos_stat.end(); ++it){
        set<POS_STAT> pos_set;
        const BOARD   &board = it->first;
        MOVE_STAT_MAP &map2  = it->second;
        for(MOVE_STAT_MAP::iterator it2 = map2.begin(); 
                it2 != map2.end(); ++it2){
        
            pos_set.insert(it2->second);
        }
        assert(pos_set.size());

        MOVE_MAKER move_maker(board);

        const POS_STAT &first_stat = *(pos_set.begin());
        const int stat_threshold = 10;
        if(first_stat.total() < stat_threshold){
            continue; // too rare position
        }
        int max_freq = first_stat.total();
        int max_percent = first_stat.percent_wins();

        total_printed++;
        BOARD t_board(board);
        t_board.reflect_in_place();
        cout << board.fen() << endl;
        cout << t_board.fen() << endl;

        bb_t zob = board.zobrist_hash();
        cout << " hash: " << zob << endl;

        hash_count_map[zob]++;
        if(hash_count_map[zob] > 1){
            cerr << "ZOB " << zob << endl;
            cout << "ZOB " << zob << endl;
        }
        

        uint8_t  best_moves[8] = {255, 255, 255, 255, 255, 255, 255, 255};
        int      n_best_moves = 0;
        

        
        for(set<POS_STAT>::iterator it3 = pos_set.begin(); it3 != pos_set.end(); it3++){
            const POS_STAT &stat = *it3;

            bool reject = false;


            MOVE move = stat.move;
            MOVE move_refl = move;
            move_refl.reflect();
            
            if(stat.total() < max_freq / 5)
                reject = true;
            if(stat.total() < stat_threshold)
                reject = true;

            if(!reject 
                    && max_percent < stat.percent_wins()
                    && stat.percent_wins() < 50
                    )
                max_percent = stat.percent_wins();

            if(stat.percent_wins() < max_percent - 10)
                reject = true;

            int move_index = move_maker.move_index(stat.move);
            assert(move_index >= 0);
            if(move_index >= 255) // probably, will not hapen 
                reject = true;

            if(n_best_moves >= 8)
                reject = true;


            if(!reject){
                best_moves[n_best_moves++] = move_index;
            }

            
            cout 
                << " " << (reject ? "-" : "+")
                << " " << stat.total()
                << " " << move
                << " / " << move_refl
                << " " << stat.wins 
                << " " << stat.draws 
                << " " << stat.losses
                << " " << stat.percent_wins() << "%"
                << " index=" << move_index
                << endl; 


            
        }

        if(n_best_moves == 0)
            continue;

        for(size_t populate_moves = n_best_moves; populate_moves < 8; populate_moves++){
            best_moves[populate_moves] = best_moves[(populate_moves - n_best_moves) % n_best_moves];
        }
        
        cout 
            << " " << (int) best_moves[0]
            << " " << (int) best_moves[1]
            << " " << (int) best_moves[2]
            << " " << (int) best_moves[3]
            << " " << (int) best_moves[4]
            << " " << (int) best_moves[5]
            << " " << (int) best_moves[6]
            << " " << (int) best_moves[7]
            << endl;
        BB moves_bb;
        moves_bb.put(0*8, 8, best_moves[0]);
        moves_bb.put(1*8, 8, best_moves[1]);
        moves_bb.put(2*8, 8, best_moves[2]);
        moves_bb.put(3*8, 8, best_moves[3]);
        moves_bb.put(4*8, 8, best_moves[4]);
        moves_bb.put(5*8, 8, best_moves[5]);
        moves_bb.put(6*8, 8, best_moves[6]);
        moves_bb.put(7*8, 8, best_moves[7]);
        BB hash1 = board.zobrist_hash();

        cout 
            << " " << (bb_t) hash1
            << endl;
        
        hash1.write(out);
        moves_bb.write(out);
    }

    cout << "total_printed: " << total_printed << " " << hash_count_map.size() << endl;
}


//# class OGDB {{{2
/// Opening Game database. 
/// This DB is a simple hash_map. 
/// The key is zobrist hash. 
/// The value is BB which contains 8 8-bit numbers. 
/// Each number is index of the move. 
class OGDB{
    typedef hash_map<bb_t, bb_t, BB_HASH> map_t;
    map_t map;
    BB m_last_result;
public:
    OGDB(){}
    OGDB(const string &ogdb_path) {read(ogdb_path);}

    /// Read OGDB from file. 
    void read(const string &ogdb_path){
        ifstream in(ogdb_path.c_str());
        if(!in){
            cerr << "No ogdb found" << endl;
            return;
        }
        // get file size
        in.seekg(0, ifstream::end);
        size_t size_in_bytes = in.tellg();
        size_t size          = size_in_bytes / (sizeof(bb_t) * 2);
        assert(size * sizeof(bb_t) * 2 == size_in_bytes);
        in.seekg(0);


        bb_t *db = new bb_t[size * 2];

        in.read((char*)db, size_in_bytes);


        hash_set<bb_t, BB_HASH> set1;

        for(size_t i = 0; i < size; i++){
            bb_t h1 = db[2*i];
            map[h1] = db[2*i+1];
            set1.insert(h1);
        }

        cerr << "Read OGDB: " 
            << (size)
            << " entries" 
            << " " << set1.size()
            << endl;

        delete db;
    }

    /// return true if the position with hash value 'hash' exists in ogdb.
    /// set m_last_result;
    bool query_board(bb_t hash){
        map_t::iterator it = map.find(hash);
        if(it == map.end())
            return false;
        m_last_result = it->second;
        return true;
    }

    /// should be called only after query_board() returned true. 
    /// returns move by index
    size_t choose_move(size_t index){
        index = index % 8;
        return m_last_result.get(index * 8, 8);
    }       
};

/// The gobal object for OGDB 
static OGDB THE_OGDB;


//# PARAM {{{1

//#struct PARAM {{{2
/// Command line parameters
struct PARAM{

    string m_prog_name;
    int    m_argc;
    char **m_argv;
    int    m_cur_arg;

    // common 
    string m_debug_file;
    int    m_trace;
    int    m_max_depth;
    int    m_max_time;
    int    m_min_depth;
    int    m_tt_bits;
    int    m_n_worker_threads;

    int    m_rand_seed;

    string m_ogdb;

    // epd
    string m_epd_file_name;

    // xboard
    
    // self

    // ogdb 
    string m_ogdb_in;
    string m_ogdb_out;



    enum{
        PARAM_COMMON,
        PARAM_XBOARD,
        PARAM_EPD, 
        PARAM_PERFT, 
        PARAM_SELF_PLAY,
        PARAM_GEN_OGDB,
        PARAM_DEBUG
    }state;

    PARAM(int argc, char **argv);
    void usage(ostream &os = cout);

    bool is(const string &s){
        Assert(m_cur_arg < m_argc);  
        bool res = (s == m_argv[m_cur_arg]);
        if(res)
            m_cur_arg++;
        return res;
    }
    
    int int_param(){
        if(m_cur_arg >= m_argc){
            usage();
        }
        return atoi(m_argv[m_cur_arg++]);
    }

    string str_param(){
        if(m_cur_arg >= m_argc){
            usage();
        }
        return m_argv[m_cur_arg++];
    }


};


//# PARAM::usage() {{{2
void PARAM::usage(ostream &os)
{
    os  << "Usage: " << m_prog_name << 
    " [common parameters] [COMMAND [command paramaters] ]\n"
    "Commands are: xboard, epd, self, debug\n"
    "Common parameters:\n"
    "\t--debug_file <file>         name of debug file to create\n"
    "\t--max_depth <N>             maximal search depth\n"
    "\t--max_time <N>              maximal time for one ply search (in seconds)\n"
    "\t--tt_bits <N>               number of entries in transposition table is 2^tt_bits\n"
    "\t--seed <N>                  random seed\n"
    "\t-j <N>                      number of worker threads\n"
    "\t--help                      show this help\n"

    ;
    exit(0);
}

//# PARAM::PARAM() {{{2
PARAM::PARAM(int argc, char **argv)
    :m_prog_name("KCChess")
    ,m_argc(argc)
    ,m_argv(argv)
    ,m_cur_arg(1)

    ,m_debug_file("")
    ,m_trace(-1)
    ,m_max_depth(7)
    ,m_max_time(-1)
    ,m_min_depth(3)
    ,m_tt_bits(18) 
    ,m_n_worker_threads(0)


{
    Assert(argc >= 1);

    m_rand_seed = (time(0) % 1000000);

    // parse all args
    state = PARAM_COMMON;
    while(m_cur_arg < m_argc){
        // cout << m_cur_arg << " " << argv[m_cur_arg] << endl;
        if(state == PARAM_COMMON){
            /***/ if(is("--debug_file")){
                m_debug_file = str_param();
            }else if(is("--max_depth")){
                m_max_depth = int_param();
                if(m_max_depth <= 2)
                    m_max_depth = 2;
            }else if(is("--min_depth")){
                m_min_depth = int_param();
                if(m_min_depth <= 2)
                    m_min_depth = 2;
            }else if(is("--max_time")){
                m_max_time = int_param();
            }else if(is("--trace")){
                m_trace = int_param();
            }else if(is("--tt_bits")){
                m_tt_bits = int_param();
            }else if(is("--seed")){
                m_rand_seed = int_param();
            }else if(is("--ogdb")){
                m_ogdb = str_param();
            }else if(is("-j")){
                m_n_worker_threads = int_param();
                if(m_n_worker_threads < 0 || m_n_worker_threads > 20){
                    cerr << "How many threads you think I can run, a?" << endl;
                    exit(1);
                }
            }else if(is("--help")){
                usage();
            }else if(is("xboard")){
                state = PARAM_XBOARD;
            }else if(is("epd")){
                state = PARAM_EPD;
            }else if(is("perft")){
                state = PARAM_PERFT;
            }else if(is("gen_ogdb")){
                state = PARAM_GEN_OGDB;
                m_ogdb_in  = str_param();
                m_ogdb_out = str_param();
            }else if(is("debug")){
                state = PARAM_DEBUG;
            }else if(is("self")){
                state = PARAM_SELF_PLAY;
            }else{
                usage();
            }
        }else if(state == PARAM_EPD){
            m_epd_file_name = str_param();
        }else if(state == PARAM_PERFT){
            m_epd_file_name = str_param();
        }else if(state == PARAM_XBOARD){
            /**/
        }else if(state == PARAM_SELF_PLAY){
        }
    }

    if(state == PARAM_COMMON)
        state = PARAM_XBOARD;

    THE_TT.resize(m_tt_bits);

}

//# TIMER {{{1
class TIMER{
    clock_t m_start;
    string  m_name;
    ostream *m_os;
public: 
    TIMER(string name = "", ostream *os = NULL) : m_name(name), m_os(os){ m_start = clock();}

    long long clocks() const {return ::clock() - m_start;}
    long long seconds() const {return clocks() / CLOCKS_PER_SEC;}
    long long mseconds() const {return 1000 * clocks() / CLOCKS_PER_SEC;}

    void flush() {m_start = clock(); }

    
    ~TIMER(){
        if(m_os){
            (*m_os) << m_name << ": " << clocks() << " " << seconds() << endl;
        }
    }
};

//# random_play() {{{1
static void random_play(int seed)
{

    BOARD board;
    board.set_new_game();
    cout << "seed = " << seed << endl;

    for(int i = 0; i < 600; i++){
        MOVE_MAKER legal_moves(board);
        cout << "[" << i << "]" << endl;
        if(legal_moves.size() == 0){
            if(legal_moves.is_mate())
                cout << "MATE" << endl << board;
            else
                cout << "Stale DRAW" << endl << board;
            return;
        }

        if(board.is_draw_by_material()){
            cout << "DRAW by material" << endl << board;
            return;
        }

        int rand_move = rand() % legal_moves.size();
        cout << legal_moves[rand_move] << endl << endl;
        board = legal_moves.moved_boards[rand_move];
//        cout << board << endl;
    }
    cout << "max number of moves exceeded" << endl << board;

}

//# perft() {{{1
//
static size_t perft_search(const BOARD &board, int depth)
{
    size_t res = 0;

    GEN_MOVE_ACTION_STORE pseudo_moves;
    size_t n_pseudo_moves = board.gen_moves(pseudo_moves);
    if(depth > 1){
        for(size_t i = 0; i < n_pseudo_moves; i++){
            MOVE::move_t the_move = pseudo_moves[i];
            BOARD new_board(board, the_move);
            if(new_board.ally_K_is_attacked()) continue;
            new_board.reflect_in_place();
            res += perft_search(new_board, depth - 1);
        }
    }else{
        for(size_t i = 0; i < n_pseudo_moves; i++){
            MOVE::move_t the_move = pseudo_moves[i];
            BOARD new_board(board, the_move);
            if(new_board.ally_K_is_attacked()) continue;
            res++;
        }

    }
    return res;
}

// PERFT (see also crafty's perft() command)
static void perft(const string &fen, int depth)
{
    BOARD board;
    string expected_str;
    vector<size_t> expected_results;
    board.read_fen(fen, expected_str);
    cout << "perft(\"" << board.fen() << "\");" << endl;
    cout << "expected: " << expected_str << endl;

    // populate expected_results;
    expected_results.push_back(0); // d=0

    for(int i = 1; ; i++){
        char pattern[10];
        sprintf(pattern, "D%d ", i);
        string::size_type pos = expected_str.find(pattern);
        if(pos == string::npos)
            break;
        string tmp = expected_str.substr(pos + strlen(pattern));
        expected_results.push_back(atoll(tmp.c_str()));
    }



    for(int i = 1; i <= depth; i++){
        clock_t t = clock();
        size_t n_nodes = perft_search(board, i);
        t = clock() - t;
        cout 
            << "d: "       << i
            << "\tn: "      << n_nodes
            << "\tt: "      << ((double)t / CLOCKS_PER_SEC) 
            << "\tnps: "  << ((double)n_nodes * CLOCKS_PER_SEC / t)
            << endl;
        if(i < (int)expected_results.size() && n_nodes != expected_results[i]){
            cerr << i << ": DOES NOT MATCH THE EXPECTED RESULT: " << expected_results[i] << endl;
            cerr << fen << endl;
            exit(1);
        }
    }
}


//# WORK_ITEM {{{1

//# class WORK_ITEM {{{2
class WORK_ITEM{
    int64_t m_id;
    MOVE_MAKER *m_item;
public: 
    WORK_ITEM(int64_t id)
        :m_id(id)
        ,m_item(0)
    {}
    void execute() {sleep((rand() % 5)  + 1);}
    int64_t id() const {return m_id;}
};


//# DISPATCHER {{{1
//# class DISPATCHER {{{2
class DISPATCHER{
    ostream &m_out;
    bool m_running;

    int m_trace;
    BOARD m_task_board;
    int   m_task_min_depth;
    int   m_task_max_depth;
    bool  m_task_reset;
    bool  m_task_ready;
    MOVE  m_task_move;
    MOVE  m_best_move;
    score_t m_task_score;
    unsigned m_search_depth;
    
    set<MOVE> m_expected_moves;


    KILLER_HEURISTIC m_killer_heuristic;

    hash_map<bb_t, int, BB_HASH> m_position_map;
  
    struct PV{  
        size_t       m_size;
        MOVE::move_t m_path[MAX_PLY];
        PV() : m_size(0){}
        void clear() {m_size = 0;}
    };

    PV m_prev_pv;

    void *Thread();
    void     solve(const BOARD &board, int min_depth, int max_depth, int max_time);

    bool order_moves(const BOARD &board, 
                     int ply, 
                     int depth, 
                     size_t ordered_moves[], 
                     MOVE::move_t pseudo_moves[],
                     size_t n,
                     score_t alpha, 
                     score_t beta,
                     PV *pv
                     );



    score_t ab_search(const BOARD &board, int ply, int depth, score_t alpha, score_t beta, PV *pv, bool allow_null);
    score_t ab_search_captures(const BOARD &board, int ply, int depth, score_t alpha, score_t beta);
    score_t ab_search_leaf(const BOARD &board, int ply, score_t alpha, score_t beta);
public:


    STATISTICS m_statistics;

    DISPATCHER(int n_workers, ostream &out, int trace);
    virtual   ~DISPATCHER() {}
    bool      has_item();
    WORK_ITEM get_item();
    void      ret_item(WORK_ITEM item);

    void      set_task(const BOARD &board, int min_depth, int max_depth, int max_time);
    void      set_expected(const set<MOVE> &expected_moves) {m_expected_moves = expected_moves;}
    void      clear_expected() {m_expected_moves.clear();}
    bool      is_ready();
    MOVE      best_move() {return m_task_move;};
    SCORE     best_score()    {return m_task_score;}

    ostream &show_stat(ostream &os) {return m_statistics.show(os);}

    /// tell the dispatcher that this position was encountered in the game 
    void register_position(const BOARD &b) {
        m_position_map[b.zobrist_hash()]++;
        m_out << "rpt: " << m_position_map.size() << " " << b.fen() << endl;
    }
    int  position_repeated(const BOARD &b) {
        hash_map<bb_t, int, BB_HASH>::iterator it = m_position_map.find(b.zobrist_hash());
        int res = 0;
        if(it != m_position_map.end())
            res = it->second;
        if(res) 
            m_out << "RPT: " << m_position_map.size() << " " << res << " " << b.fen() << endl;
        return res;
    }
};

//# DISPATCHER::DISPATCHER {{{2
DISPATCHER::DISPATCHER(int n_workers, ostream &out, int trace)
        :m_out(out)
        ,m_running(false)
        ,m_trace(trace)
        ,m_task_reset(false)
        ,m_task_move(0)
        ,m_best_move(0)
        ,m_task_score(0)
{
#ifndef HAVE_JTHREAD
    Assert(n_workers == 0);
#endif
    if(n_workers == 0){
        m_task_ready = true;
        return;
    }
}



//# DISPATCHER::set_task() {{{2
void DISPATCHER::set_task(const BOARD &board, int min_depth, int max_depth, int max_time)
{
//    cout << "set_task: try\n";
    {
//        cout << "set_task: got\n";
        m_task_board = board;
        m_task_min_depth = min_depth;
        m_task_max_depth = max_depth;
        m_task_reset = true;
        m_task_ready = true;
        solve(m_task_board, m_task_min_depth, m_task_max_depth, max_time);
    }
//    cout << "set_task: unlock\n";
}

//# DISPATCHER::is_ready() {{{2
bool DISPATCHER::is_ready()
{
    bool res;
    {
//        cout << "is_read: try\n";
        res = m_task_ready;
//        cout << "is_read: got\n";
    }
//    cout << "is_read: unlock\n";
    return res;
}


//# DISPATCHER::get_item() {{{2
WORK_ITEM DISPATCHER::get_item()
{
    static int64_t item_id = 0;
    item_id++;
    WORK_ITEM item(item_id);
    cout << "+++: " << item.id() << endl;
    return item;
}

//# DISPATCHER::ret_item() {{{2
void DISPATCHER::ret_item(WORK_ITEM item)
{
    cout << "---: " << item.id() << endl;
}

//# DISPATCHER::has_item() {{{2
bool DISPATCHER::has_item()
{
//    return (rand() % 5) > 0;
    return false;
}

//# DISPATCHER::solve() {{{2
void DISPATCHER::solve(const BOARD &board, int min_depth, int max_depth, int max_time)
{
    MOVE_MAKER moves(board);
    assert(max_depth >= 2);
    size_t n = moves.size();

    if(n == 0){
        m_task_move = MOVE(0);
        m_task_score = 0;
        return;
    }

    // try OGDB
    if(THE_OGDB.query_board(board.zobrist_hash())){
        size_t task_move_num = THE_OGDB.choose_move(rand());
        m_task_move     = moves[task_move_num];
        m_task_score    = 0;
        m_out << "OGDB: " << m_task_move << endl;
        return;
    }



    m_killer_heuristic.reset();
    TIMER timer;

    m_prev_pv.clear();

    int consecutive_succ = 0;

    score_t best_score = 0;
    // do the search 
    for(int depth = min_depth; depth <= max_depth; depth++){
        m_search_depth = depth;
        score_t alpha = SCORE::MIN, beta = SCORE::MAX;
        m_best_move = moves[0];
        PV pv;

        bool do_mtdf = true;
        while(0 && do_mtdf){ // not a loop
            score_t mid = best_score;
            score_t lb = mid - SCORE::SCORE_P*2;
            score_t ub = mid + SCORE::SCORE_P*2;
            score_t s;

            s = ab_search(board, 0, depth * ONE_PLY_DEPTH, lb, lb + 1, &pv, false);
            m_out << "mtdf/l: " << lb << '/' << SCORE(s) << " " << timer.mseconds() << endl;

            if(s <= lb){
                beta = lb;
                break;
            }

            s = ab_search(board, 0, depth * ONE_PLY_DEPTH, ub, ub + 1, &pv, false);
            m_out << "mtdf/u: " << ub << '/' << SCORE(s) << " " << timer.mseconds() << endl;

            if(s > ub){
                alpha = ub;
                break;
            }
    
            score_t u = ub, l = lb;

            while(0 && u - l > 128){
                score_t m = (u + l) / 2;
                score_t w = 4;
                s = ab_search(board, 0, depth * ONE_PLY_DEPTH, m-w, m+w, &pv, false);
                m_out << "mtdf/m: " << (m-w) << '/' << (m+w) << '/' << SCORE(s) << " " << timer.mseconds() << endl;
                if     (s == m-w) {u = m-w;}
                else if(s == m+w) {l = m+w;}
                else break;
            }
            best_score = s;
            alpha = l;
            beta  = u;
            break;
        }


//        if(alpha != beta)
//        m_out << "AB: " << alpha << '/' << beta << endl;
            best_score = ab_search(board, 0, depth * ONE_PLY_DEPTH, alpha, beta, &pv, false);


        m_prev_pv = pv;
        bool found_expected_move = m_expected_moves.count(m_best_move);


        m_out 
            << (found_expected_move ? "*" : " ")
            << ""      << timer.mseconds() << "\t" 
            << "dep "  << depth << "\t" 
            << "sc "   << SCORE(best_score) << "\t" 
            << "mv "   << m_best_move << "\t" 
            ;
        m_out << "pv ";
        BOARD tmp_board = board;
        for(size_t ply = 0; ply < pv.m_size; ply++){
            MOVE move = pv.m_path[ply];
            MOVE_MAKER moves(tmp_board);
            int move_index = moves.move_index(move);
            if(move_index < 0){
                m_out << "???";
                break;
            }
            tmp_board.make_SAN(m_out, move) << " ";
            tmp_board = moves.moved_boards[move_index];
        }
        m_out << endl;


        if(best_score != SCORE::MAX){
        //    assert(pv.m_size > 0);
        //    assert(pv.m_path[0] == m_best_move.raw());
        }


        if(best_score == SCORE::MAX || best_score == SCORE::MIN){
            break;
        }

        if(max_time > 0 && timer.seconds() >= max_time){
            break;
        }

        if(found_expected_move) consecutive_succ++;
        else                    consecutive_succ = 0;

        if(consecutive_succ >= 4)
            break;

    }

    // report the result
    m_task_ready = true;
    m_task_move  = m_best_move;
    m_task_score = best_score;

}

//# DISPATCHER::ab_search_leaf() {{{2
score_t DISPATCHER::ab_search_leaf(const BOARD &board, int ply, score_t alpha, score_t beta)
{
    MOVE::move_t best_move = 0;
    int n_legal_moves = 0;
    score_t best_score = SCORE::MIN;

    DO_DEBUG(m_trace >= ply, m_out << "ab_leaf" << ply << " " << endl;);

    // first of all try killer move. If it works, no reason to generate all other moves
    MOVE::move_t killer = m_killer_heuristic.killer(ply);
    if(board.is_pseudo_move(killer)){
        BOARD leaf_board(board, killer);
        if(!leaf_board.ally_K_is_attacked()){
            n_legal_moves++;
            score_t killer_score = leaf_board.evaluate(alpha, beta);
            best_score = max(best_score, killer_score);
            if(killer_score > alpha){
                alpha = killer_score;
                best_move = killer;
            }
        }
    }


    // see how often we cut with the killer
//    m_statistics.increment_ab_cut(n_legal_moves);



    GEN_MOVE_ACTION_STORE pseudo_moves;
    size_t n = alpha < beta ? board.gen_moves(pseudo_moves) : 0;

    // search leaf nodes
    size_t i;
    for(i = 0; i < n; i++){
        MOVE::move_t the_move = pseudo_moves[i];
        // skip killer, we already done with it. 
        if(the_move == killer) continue;

        // check if this one is legal 
        BOARD leaf_board(board, the_move);

        bool legality_computed = false;

        if(n_legal_moves == 0){
            if(leaf_board.ally_K_is_attacked())
                continue;
            legality_computed = true;
        }

        n_legal_moves++; // not really a legal yet
        
        score_t leaf_score  = leaf_board.evaluate(alpha, beta);

        if(leaf_score > alpha){
            if(!legality_computed && leaf_board.ally_K_is_attacked()){
                continue;
            }
            best_score = leaf_score;
            alpha = leaf_score;
            best_move = the_move;
            if(alpha >= beta){
                break;
            }
        }
    }

//    m_statistics.increment_ab_cut(n);

    m_statistics.increment_search(ply, n_legal_moves);

    if(n_legal_moves == 0){
        DO_DEBUG(m_trace >= ply, m_out << "ABL" << ply << " " << "no legal moves" << endl;);
        return (board.ally_K_is_attacked() ? SCORE::MIN : SCORE::MED);
    }


    m_killer_heuristic.add_move(best_move, ply);

    return best_score;
}
//# DISPATCHER::order_moves() {{{2
/**
    Order the moves, return true if mate is found.
    TODO

  */
bool DISPATCHER::order_moves(
        const BOARD &board, 
        int ply, 
        int depth, 
        size_t ordered_moves[], 
        MOVE::move_t pseudo_moves[], 
        size_t n,
        score_t alpha, 
        score_t beta,
        PV *pv
        )
{
    PV new_pv;
    size_t sort_start = 0;

    // try pv moves 
/*
    if(ply < (int)m_prev_pv.m_size){
        MOVE pv_move = m_prev_pv.m_path[ply];
        for(size_t i = sort_start; i < n; i++){
            if(ordered_moves[i] == pv_move.raw()){
                swap(ordered_moves[sort_start], ordered_moves[i]);
                sort_start++;
                break;
            }
        }
    }
    */

    // put all killer moves first
    for(size_t i = sort_start; i < n; i++){
        if(m_killer_heuristic.is_killer(ply, pseudo_moves[ordered_moves[i]])){
            swap(ordered_moves[sort_start], ordered_moves[i]);
            sort_start++;
        }
    }


    // Internal deepening 
    // perform search with smaller depth 
    if(depth > 2 * ONE_PLY_DEPTH){
        score_t scores[MAX_N_MOVES];
        depth -= 3*ONE_PLY_DEPTH;
        size_t sort_end = n;
        assert(alpha < beta);
        

        for(size_t i = sort_start; i < n; i++){
            size_t move = ordered_moves[i];
            MOVE::move_t the_move = pseudo_moves[move];

            BOARD new_board(board, the_move);
            if(new_board.ally_K_is_attacked()){
                scores[i] = SCORE::MIN;
                continue;
            }
            new_board.reflect_in_place();

            score_t score = -ab_search(new_board, ply + 1, depth, -beta, -alpha, &new_pv, true);

            if(0 && DEBUG && m_trace >= ply){
//                score_t score1 = -ab_search(new_board, ply + 1, depth+1*ONE_PLY_DEPTH, -beta, -alpha);
//                score_t score2 = -ab_search(new_board, ply + 1, depth+2*ONE_PLY_DEPTH, -beta, -alpha);
                m_out << "om" << ply
                    << " " << MOVE(the_move) 
                    << " " << SCORE(score) 
                    << " " << SCORE(alpha) << "/" << SCORE(beta)
//                    << " " << SCORE(score1)
//                    << " " << SCORE(score2)
                    << endl;
            }

 
            scores[i] = score;
            if(score > alpha)
                alpha = score;
        }

        // sort scores: handle only few max values, don't touch others 
        size_t pos = sort_start;
        while(pos < std::min(size_t(30), sort_end)){
            score_t max_score = scores[pos];
            size_t max_index = pos;
            for(size_t i = pos+1; i < sort_end; i++){
                if(max_score < scores[i]){
                    max_score = scores[i];
                    max_index = i;
                }
            }
            std::swap(scores[pos], scores[max_index]);
            std::swap(ordered_moves[pos], ordered_moves[max_index]);
            pos++;
        }

#if DEBUG
        if(m_trace >= ply){
            bool has_max = false;
            m_out << "OM" << ply << " ";
            for(size_t i = sort_start; i < std::min(size_t(10), sort_end); i++){
                m_out << SCORE(scores[i]) << "/" << MOVE(pseudo_moves[ordered_moves[i]]) << " ";
                if(scores[i] == SCORE::MAX)
                    has_max = true;
            }
            m_out << endl;
            if(has_max){
                m_out << "has_max " << ply << endl;
            }
        }
#endif
    }
    return false;
}

//# DISPATCHER::ab_search_captures() {{{2
/**
    Alpha-beta negamax 'quiescence' search (biggest captures and promotions only). 
*/
score_t DISPATCHER::ab_search_captures(const BOARD &board, int ply, int depth, score_t alpha, score_t beta)
{

    m_statistics.increment_search(ply, 1);
    score_t score = board.evaluate(alpha, beta);
    if(score > alpha){
        alpha = score;
        if(score >= beta){
            return alpha;
        }
    }



    score_t max_win = 0;
    BB mask;  { max_win = SCORE::SCORE_Q;  mask = board.enemy_piece_bb(Q); }
    if(!mask) { max_win = SCORE::SCORE_R;  mask = board.enemy_piece_bb(R); }
    if(!mask) { max_win = SCORE::SCORE_BN; mask = board.enemy_piece_bb(B) | board.enemy_piece_bb(N); }
    if(!mask) { max_win = SCORE::SCORE_P;  mask = board.enemy_piece_bb(P); }

    if(score + max_win <= alpha){
        // even if we capture the biggest piece, we won't reach alpha
        return alpha;
    }

    if(!mask){
        // we can't capture anyone big 
        return alpha;
    }

    BB t = mask;
    POS pos = t.pop_first_one();
    if(!t){
       if(!board.ally_attackers(pos)){
           // there is only one big piece to capture and it is not attacked by anyone 
           return alpha;
       }
    }

    GEN_MOVE_ACTION_STORE_CAPTURES_AND_PROMO pseudo_moves(mask);
    size_t n = board.gen_moves(pseudo_moves);
    size_t i;
    for(i = 0; i < n; i++){
        MOVE::move_t the_move = pseudo_moves[i];
        BOARD new_board(board, the_move);
        if(new_board.ally_K_is_attacked()) continue;
        new_board.reflect_in_place();
//        score = -ab_search_captures(new_board, ply + 1, depth+1, -beta, -alpha);
        score = -new_board.evaluate(-beta, -alpha);
        m_statistics.increment_search(ply, 1);
        if(score > alpha){
            alpha = score;
            if(score >= beta){
                break;
            }
        }
    }
//    m_statistics.increment_ab_cut(n);
    return alpha;
}
//# DISPATCHER::ab_search() {{{2
/**
    Alpha-beta negamax. 

  */
score_t DISPATCHER::ab_search(const BOARD &board, int ply, int depth, score_t alpha, score_t beta, PV *pv, bool allow_null)
{
    PV new_pv;
    score_t orig_alpha = alpha;
    if(ply >= MAX_PLY)
        return beta;

    bool has_pv = false; // trying principal variation search 

    if(alpha >= beta)
        return alpha;


    if(depth <= ONE_PLY_DEPTH){
//        return ab_search_leaf(board, ply, alpha, beta);
        return ab_search_captures(board, ply, 0, alpha, beta);
    }
    DO_DEBUG(m_trace >= ply, m_out << "ab" << ply << " " << depth << " " 
            << SCORE(alpha) << " " << SCORE(beta) << endl;);



    bool use_tt = depth >= 1 * ONE_PLY_DEPTH;
    bb_t zobrist(0); 
    TTE::TYPE tte_type = TTE::ALPHA;

    if(use_tt){
        // find this node in TT
        zobrist = board.zobrist_hash();
        TTE tte = THE_TT.get(zobrist);
        if(tte.get_lock()   == zobrist
            && tte.get_depth() >= depth
                ){
            TTE::TYPE type = tte.get_type();
            score_t tte_score = tte.get_score();
            if(type == TTE::EXACT){
                DO_DEBUG(m_trace >= ply, m_out << "tt_e " << ply << endl;);
                return tte_score;
            }
            if(type == TTE::ALPHA && tte_score <= alpha){
                DO_DEBUG(m_trace >= ply, m_out << "tt_a " << ply << endl;);
                return alpha;
            }
            if(type == TTE::BETA  && tte_score >= beta){
                DO_DEBUG(m_trace >= ply, m_out << "tt_b " << ply << endl;);
                return beta;
            }
        }
    }


    // search further
    MOVE::move_t best_move = 0;
    int n_legal_moves = 0;



    // null move
    if(allow_null 
            && depth >= 3 * ONE_PLY_DEPTH
            && !board.ally_K_is_attacked()){
        PV tmp_pv;
        BOARD null_board(board);
        null_board.reflect_in_place();
        null_board.clear_en_passant();
        score_t null_score = -ab_search(null_board, ply + 1, depth - 3 * ONE_PLY_DEPTH, -beta, -beta+1, &tmp_pv, false);
        if(null_score >= beta)
            return beta;
    }

    GEN_MOVE_ACTION_STORE pseudo_moves;

    // first of all try killer move(s). If it works, no reason to generate all other moves
    MOVE::move_t killer = m_killer_heuristic.killer(ply, 0);
    if(board.is_pseudo_move(killer)){
        BOARD new_board(board, killer);
        if(!new_board.ally_K_is_attacked()){
            n_legal_moves++;
            new_board.reflect_in_place();
            score_t killer_score =  -ab_search(new_board, ply + 1, depth-ONE_PLY_DEPTH, -beta, -alpha, &new_pv, true);

            DO_DEBUG(m_trace >= ply, m_out << "ab" << ply << " " << "killer" 
                   << " " << killer_score << " " << MOVE(killer) << endl;);
            if(killer_score > alpha){
                alpha = killer_score;
                best_move = killer;
                tte_type = TTE::EXACT;
                if(killer_score < beta)
                {
                    // update PV
                    pv->m_size = new_pv.m_size + 1;
                    pv->m_path[0] = best_move;
                    memcpy(pv->m_path + 1, new_pv.m_path, new_pv.m_size * sizeof(MOVE));
                }
            }
        }
    }


    if(alpha >= beta){
        DO_DEBUG(m_trace >= ply, m_out << "AB" << ply << " " << "killer"  << endl;);
    }




    if(alpha < beta){
        size_t i;
        size_t n = board.gen_moves(pseudo_moves);
        size_t ordered_moves[MAX_N_MOVES];
        for(i = 0; i < n; i++){
            ordered_moves[i] = i;
        }
        DO_DEBUG(m_trace >= ply, m_out << "ZZ" << ply << " " << SCORE(alpha) << "/" << SCORE(beta) << endl;);
        order_moves(board, ply, depth, ordered_moves, pseudo_moves.raw(), n, alpha, beta, pv);

        // search recursively 
        for(i = 0; i < n; i++){
            size_t move = ordered_moves[i];
            MOVE::move_t the_move = pseudo_moves[move];

            // skip the killer, we already tried it
            if(the_move == killer) continue;

            BOARD new_board(board, the_move);
            if(new_board.ally_K_is_attacked())
                continue;
            n_legal_moves++;


            new_board.reflect_in_place();

            score_t score = 0;
            bool need_full_search = true;
            if(has_pv){
                score = -ab_search(new_board, ply + 1, depth-ONE_PLY_DEPTH, -alpha-1, -alpha, &new_pv, true);
                if(score <= alpha || score >= beta)
                    need_full_search = false;
            }
            if(need_full_search){
                score = -ab_search(new_board, ply + 1, depth-ONE_PLY_DEPTH, -beta, -alpha, &new_pv, true);
            }

            DO_DEBUG(m_trace >= ply, 
                    cout << "ab" << ply << "\t" << MOVE(the_move) << 
                    "\t" << SCORE(score) << "\t" << SCORE(alpha) << "/" << SCORE(beta)  << endl;
                    );


            if(score > alpha){
                has_pv = true;
                alpha = score;
                best_move = the_move;

                tte_type = TTE::EXACT;


                if(alpha >= beta){
                    m_killer_heuristic.add_move(the_move, ply);
                    break;
                }

                // update PV
                pv->m_size = new_pv.m_size + 1;
                pv->m_path[0] = best_move;
                memcpy(pv->m_path + 1, new_pv.m_path, new_pv.m_size * sizeof(MOVE));
            }


        }
//        m_statistics.increment_ab_cut(i);
        m_statistics.increment_ab_cut(alpha > orig_alpha);
//        if(alpha == orig_alpha)
//            m_statistics.increment_ab_cut(i);
#if DEBUG > 0
        if(alpha < beta){
            DO_DEBUG(m_trace >= ply, m_out << "AB" << ply << " " 
                    << "no cut" << endl;);
        }else{
            int approx_n_tries = n_legal_moves <= 4
                ? n_legal_moves : (((n_legal_moves+19)/20)*20);
            DO_DEBUG(m_trace >= ply, m_out << "AB" << ply << " " 
                    << "CUT after ~" <<  approx_n_tries << " tries"  << endl;);

        }
#endif

    }

    // count how many time we made cut with a killer 
//    m_statistics.increment_ab_cut(m_killer_heuristic.is_killer(ply, best_move));

    if(ply == 0)
        m_best_move = best_move;

//    if(n > 0 && depth > 2*ONE_PLY_DEPTH)
//    m_statistics.increment_ab_cut(i);


    m_statistics.increment_search(ply, n_legal_moves);



    if(use_tt)
    {
        if(alpha >= beta){
            tte_type = TTE::BETA;
            alpha = beta;
        }
        // put new entry into TT
        TTE new_tte(zobrist, alpha, tte_type, depth, best_move);
        THE_TT.put(zobrist, new_tte);
    }

    if(n_legal_moves == 0){
        DO_DEBUG(m_trace >= ply, m_out << "AB" << ply << " " << "no legal moves"  << endl;);
        return (board.ally_K_is_attacked() ? SCORE::MIN : SCORE::MED);
    }

    // done
    return alpha;
}

#if 0
    // check for repeates 
    bool avoid_repeats[MAX_N_MOVES];
    if(check_repeats){
        // check if one of the positions repeated twice: 
        // check for repeats for depth 2 
        for(size_t i = 0; i < n; i++){
            size_t move = ordered_moves[i];
            BOARD &b = moved_boards[move];
            avoid_repeats[move] = false;
            int repeats = position_repeated(b);
            if(repeats >= 1){
                m_out << "repeats d=1" << repeats << "\t" << b.fen() << endl;
                avoid_repeats[move] = true;
            }else{
                MOVE_MAKER moves(b);
                for(size_t j = 0; j < moves.size(); j++){
                    if(position_repeated(moves.moved_boards[j])){
                        m_out << "repeats d=2" << repeats << "\t" << moves.moved_boards[j].fen() << endl;
                        avoid_repeats[move] = true;
                        break;
                    }
                }
            }
        }
    }
#endif


//# CLI {{{1

//# class CLI {{{2
class CLI{
    const PARAM &m_param;
    istream &in;
    ostream &out;
    ostream &err;

    string cmd_line, cmd_name, cmd_arg;

    bool random;

    bool force_mode;

    BOARD board;

    stack<BOARD> state_stack;

    DISPATCHER m_dispatcher;
public: 
        CLI(const PARAM &param, 
                istream &in_arg, 
                ostream &out_arg,
                ostream &err_arg)
            :m_param(param)
            ,in(in_arg)
            ,out(out_arg)
            ,err(err_arg)
            ,random(false)
            ,force_mode(false)
            ,m_dispatcher(param.m_n_worker_threads, err_arg, param.m_trace)
        {}

        void run();

        void cmd_exit()    {::exit(0);}
        void cmd_void()    {}
        void cmd_not_supported() {err << "Not supported: " << cmd_name << endl;}

        void cmd_random() {random = !random;}


        void cmd_new() {
            random = false;
            board.set_new_game();
            err << "new: " << endl;
            err << board << endl;
        }

        void cmd_force() { force_mode = true;}

        void cmd_go(){
            force_mode = false;
            tell_move();
        }


        void cmd_protover() {out << "feature playother=1 colors=0 done=1 sigint=0 sigterm=0" << endl;}

        bool cmd_parse_move();

        void cmd_undo(){
            Assert(!state_stack.empty());
            board = state_stack.top();
            state_stack.pop();
            err << "UNDO: " << board << endl;
        }


        void tell_move();

};


//# CLI::tell_move() {{{2
void CLI::tell_move()
{
    err << "CLI::tell_move() " << endl;
    MOVE_MAKER legal_moves(board);

    if(legal_moves.size() == 0){
        if(board.ally_K_is_attacked()){
            out << "RESULT 1-0" << endl;
            err << "I lost"  << endl;
            return;
        }else{
            out << "RESULT 1/2-1/2" << endl;
            err << "I have no legal moves" << endl;
            return;
        }
    }
#if 0
    // do a random move
    int rand_move = rand() % legal_moves.size();
    bool is_reflected = board.is_reflected();

    out << "move " << legal_moves[rand_move].coordinate_notation(is_reflected) << endl;

    state_stack.push(board);
    board = legal_moves.moved_boards[rand_move];

    err << "My move: " << legal_moves[rand_move].coordinate_notation(is_reflected) << endl << board << endl;
#endif

    // MOVE
    m_dispatcher.clear_expected();
    m_dispatcher.set_task(board, m_param.m_min_depth, m_param.m_max_depth, m_param.m_max_time);

    while(!m_dispatcher.is_ready()){
        sleep(1);
        err << "...\n";
    }

    MOVE move = m_dispatcher.best_move();
    int move_num = legal_moves.move_index(move);
    assert(move_num >= 0);
    bool is_reflected = board.is_reflected();
    out << "move " << move.coordinate_notation(is_reflected) << endl;


    state_stack.push(board);
    board = legal_moves.moved_boards[move_num];
    m_dispatcher.register_position(board);

    err << "My move: " << move.coordinate_notation(is_reflected) << endl << board << endl;
}

//# CLI::cmd_parse_move() {{{2
bool CLI::cmd_parse_move()
{
    PIECE promo = K;

    // TODO
    if(state_stack.size() > 500){
        err << "too many moves" << endl;
        exit(0);
    }


    unsigned row1, col1, row2, col2;
    if(cmd_name.size() == 5){
        char promo_name = cmd_name[4];
        switch(promo_name){
            case 'q': promo = Q; break;
            case 'n': promo = N; break;
            case 'r': promo = R; break;
            case 'b': promo = B; break;
            default : return false;
        }
    }else if(cmd_name.size() != 4){
        return false;
    }

    col1 = cmd_name[0] - 'a';
    row1 = cmd_name[1] - '1';
    col2 = cmd_name[2] - 'a';
    row2 = cmd_name[3] - '1';

    if(board.is_reflected()){
        row1 = 7 - row1;
        row2 = 7 - row2;
    }

    if(col1 >= 8 || col2 >= 8 || row1 >= 8 || row2 >= 8){
        return false;
    }

    POS from(row1, col1);
    POS to  (row2, col2);


    MOVE_MAKER legal_moves(board);

    MOVE m(0);
    size_t i;
    for(i = 0; i < legal_moves.size(); i++){
        m = legal_moves[i];
        if(m.from() != from) continue;
        if(m.to() != to) continue;
        if(m.get_promot_piece() != promo) continue;
        // TODO:promo
        break;
    }


    if(i == legal_moves.size()){
        err << "rejected move " << " " << cmd_name << endl << board << endl;
        out << "Illegal move: " << cmd_name << endl;
        return true;
    }

    err << "opponent move made: " << m << endl << legal_moves.moved_boards[i] <<  endl;

    // set the board to the new state
    state_stack.push(board);
    board = legal_moves.moved_boards[i];
    m_dispatcher.register_position(board);
    
    // make my own move
    if(!force_mode)
        tell_move();

    return true;

}

//# CLI::run() {{{2
void CLI::run()
{
    size_t i;
    err << "seed = " << m_param.m_rand_seed << endl;
    while(in.good() && !in.eof()){
        cmd_line = read_line(in);
        // trim leading spaces
        for(i = 0; i < cmd_line.size() && isspace(cmd_line[i]); i++);
        cmd_line = cmd_line.substr(i);

        // find the command name
        for(i = 0; i < cmd_line.size() && !isspace(cmd_line[i]); i++); 
        cmd_name = cmd_line.substr(0, i);

        err << "***" << cmd_name << " --- " << cmd_arg << endl;
        
        // find the arguments
        for(; i < cmd_line.size() && isspace(cmd_line[i]); i++);
        cmd_arg  = cmd_line.substr(i);

        /***/ if(cmd_name == "exit")      cmd_exit();
        else  if(cmd_name == "q")         cmd_exit();
        else  if(cmd_name == "quit")      cmd_exit();
        else  if(cmd_name == "xboard")    cmd_void();
        else  if(cmd_name == "protover")  cmd_protover();
        else  if(cmd_name == "new")       cmd_new();
        else  if(cmd_name == "variant")   cmd_not_supported();
        else  if(cmd_name == "time")      cmd_void(); //cmd_not_supported();
        else  if(cmd_name == "otim")      cmd_void(); //cmd_not_supported();
        else  if(cmd_name == "force")     cmd_force();
        else  if(cmd_name == "undo")      cmd_undo();
        else  if(cmd_name == "go")        cmd_go();
        else  if(cmd_parse_move())        ;
        else{
            err << "UNKNOWN" << endl;
        }
    }
}

}  // namespace KCChess

//# main() {{{1
/**
    @callgraph
  */
int KCChess_main(int argc, char **argv)
{
    using namespace KCChess;
    assert(sizeof(BOARD) == 10*sizeof(bb_t));

    
    PARAM param(argc, argv);

    srand(param.m_rand_seed);

    if(param.m_ogdb.size() > 0)
        THE_OGDB.read(param.m_ogdb);

    // XBOARD
    if(param.state == PARAM::PARAM_XBOARD){
        ofstream err_file(param.m_debug_file.c_str());

        ostream &err = err_file.good() ? err_file : cerr;
        err << "xboard\n";
        cout.setf(ios::unitbuf);
        CLI cli(param, cin, cout, err);
        cli.run();
        return 0;
    }

    // SELF
    if(param.state == PARAM::PARAM_SELF_PLAY){
        random_play(param.m_rand_seed);
        cout << "seed = " << param.m_rand_seed << endl;
        return 0;
    }

    if(param.state == PARAM::PARAM_PERFT){
        vector<string> epd_vec;
        if(param.m_epd_file_name == "startpos"){
            string start_pos_perft(BOARD::startpos_fen());
            start_pos_perft += ";D1 20 ;D2 400 ;D3 8902 ;D4 197281 ;D5 4865609 ;D6 119060324";
            epd_vec.push_back(start_pos_perft);
        }else{
            ifstream in(param.m_epd_file_name.c_str());
            if(!in.good()){
                cerr << "can't open epd file " << endl;
                exit(1);
            }
            read_string_vector(epd_vec, in);
        }

        for(size_t i = 0; i < epd_vec.size(); i++){
            const string &fen = epd_vec[i];
            perft(fen, param.m_max_depth);
        }

        return 0;
    }

    // EPD
    if(param.state == PARAM::PARAM_EPD){
        TIMER main_timer("main", &cout);
        int total_passed = 0;
        int total_failed = 0;
        int total_not_parsed = 0;
        int64_t total_nodes = 0;
        string in_name = param.m_epd_file_name;
        vector<string> epd_vec;
        if(in_name == "-"){
            read_string_vector(epd_vec, cin);
        }else{
            ifstream in(in_name.c_str());
            if(!in.good()){
                cerr << "can't open epd file " << endl;
                exit(1);
            }
            read_string_vector(epd_vec, in);
        }



        DISPATCHER dispatcher(param.m_n_worker_threads, cout, param.m_trace);

        for(size_t i = 0; i < epd_vec.size(); i++){
//            THE_TT.reset(); // we need to reset THE_TT here if we want independant results for each epd 
            TIMER local_timer;
            string epd_commands;
            BOARD board;
            if(!board.read_fen(epd_vec[i], epd_commands)){
                cout << "failed to parse: " <<  epd_vec[i] << endl;
                continue;
            }

            string::size_type pos;

            bool negative_test = false;
            // strip 'bm '
            pos = epd_commands.find("bm ");
            if(pos != string::npos){
                epd_commands = epd_commands.substr(pos + 3);
            }else{
                pos = epd_commands.find("wm ");
                if(pos != string::npos){
                    negative_test = true;
                    epd_commands = epd_commands.substr(pos + 3);
                }
            }
            // remove other commands 
            pos = epd_commands.find(';');
            if(pos != string::npos)
                epd_commands = epd_commands.substr(0, pos);
//            cout << epd_commands << endl;

            set<MOVE> expected_moves;
            string t_str = epd_commands;
            // iterate over space-separated moves
            while(!t_str.empty()){
                string one_move;
                pos = t_str.find(' ');
                if(pos == string::npos){
                    one_move = t_str;
                    t_str.clear();
                }else{
                    one_move = t_str.substr(0, pos);
                    t_str = t_str.substr(pos+1);
                }
//                cout << '|' << one_move << '|' << endl;
                MOVE known_best_move = board.parse_SAN(one_move);
                if(!known_best_move.is_illegal()){
//                    cout << "expect " << known_best_move << endl;
                    expected_moves.insert(known_best_move);
                }
            }
            dispatcher.set_expected(expected_moves);
            dispatcher.set_task(board, param.m_min_depth, param.m_max_depth, param.m_max_time);

            while(!dispatcher.is_ready()){
                sleep(1);
                cout << "...\n";
            }

            MOVE best_move = dispatcher.best_move();

            size_t n_searched_nodes = dispatcher.m_statistics.tot_search();
            total_nodes += n_searched_nodes;

            cout << "Best move: " << best_move << "   ---   expected "  << epd_commands  << endl;

            bool passed = false;

            if(!expected_moves.empty()){
                if((expected_moves.count(best_move) != 0) == !negative_test){
                    passed = true;
                    cout << "PASSED"; 
                    total_passed++;
                }else{
                    total_failed++;
                    cout << "FAILED";
                }
                cout << " " << local_timer.mseconds() << "\t" << epd_vec[i] << endl;
            }else{
                total_not_parsed++;
            }


            cerr << "                                                                              \r";
            cerr 
                 << (passed ? "+ " : "- ")
                 << total_passed << '/' << (i+1) << "\t"
                << "ratio: " << (CLOCKS_PER_SEC * (((double)n_searched_nodes / 1000)/ local_timer.clocks())) << "\t";
            dispatcher.show_stat(cerr) << "\r";

            dispatcher.m_statistics.flush();
        }
        cerr << endl;
        cout << "PASS RATE: " << total_passed << "/" << epd_vec.size() << "\t";
        if(total_not_parsed)
            cout << "NO PARSED: " << total_not_parsed << "\t";
       
        cout << "ratio: " << (CLOCKS_PER_SEC * (((double)total_nodes / 1000)  / main_timer.clocks())) << "\t";
        cout << "tot: " << (total_nodes / 1000000) << " ";
        return 0;
    }

    if(param.state == PARAM::PARAM_GEN_OGDB){
        generate_opening_db(param.m_ogdb_in, param.m_ogdb_out, param.m_max_depth);
        return 0;
    }

    if(param.state == PARAM::PARAM_DEBUG){
        //        OGDB ogdb("ogdb");
        PGN_READER reader(cin);
        int i = 0;
        while(reader.read_one_game() || reader.skip_corrupted_game()){
            i++;
            BOARD board;
            board.set_new_game();
            size_t n = reader.n_moves();
            for(size_t j = 0; j < n; j++){
                MOVE move = reader.move(j);
                cout << (j+1) << "\t" << board.fen() << endl;
                MOVE_MAKER maker(board);
                for(size_t k = 0; k < maker.size(); k++){
                    cout << "\t\t" << maker.moved_boards[k].fen() << endl;
                }

                BOARD new_board(board, move);
                new_board.reflect_in_place();
                board = new_board;
            }
        }   
        return 0;
    }   
    Assert(0);
    return 0;
}

namespace KCChess{
// CONSTANT_TABLE::random_values {{{1
const bb_t CONSTANT_TABLE::random_values[4096] = 
{
 7749363893351949254ULL, 7222815480849057907ULL, 8408462745175416063ULL, 3091884191388096748ULL, 2562019500164152525ULL, 4403210617922443179ULL, 3364542905362882299ULL, 8782769017716072774ULL, // 7
 5863405773976003266ULL, 1306053050111174648ULL,  150346236956174824ULL, 1265737889039205261ULL, 1445109530774087002ULL, 1197105577171186275ULL, 9213452462461015967ULL, 4730966302945445786ULL, // 15
 5650605098630667570ULL, 5880381756353009591ULL, 4552499520046621784ULL, 2697991130065918298ULL, 4858364911220984157ULL, 3691457481531040535ULL, 2613117305472506601ULL, 7449943749836318932ULL, // 23
  643378865959570610ULL, 4851450802679832774ULL, 1772859812839988916ULL, 8210946489571640849ULL,  591875965497384322ULL, 4221553402965100097ULL, 2197744667347238205ULL, 8321400714356781191ULL, // 31
 2459557415995497961ULL, 3460673533926954145ULL, 4727304344741345505ULL, 4903203917250634599ULL, 4036494370831490817ULL, 8585205035691420311ULL, 2622143824319236828ULL, 5902762718897731478ULL, // 39
 6344401509618197560ULL, 4059247793194552874ULL, 7648030174294342832ULL, 2111858627070002939ULL, 3231502273651985583ULL, 8821862535190318932ULL, 6062559696943389464ULL, 4054224670122353756ULL, // 47
 3674929609692563482ULL, 6310802012126231363ULL, 4450190829039920890ULL, 8764531173541462842ULL, 1361923252301505833ULL, 5912924843615600614ULL, 5714768882048811324ULL, 7249589769047033748ULL, // 55
 4123157012528828376ULL, 1729687638268160097ULL, 5132287771298228729ULL, 1564349257200314043ULL,  951586254223522969ULL, 4569664949094662293ULL, 9082730968228181483ULL, 6312891027251024051ULL, // 63
 6915415788559031791ULL, 2713150456497618688ULL, 5390954890749602465ULL, 1405547745908296421ULL, 1157301728707637259ULL, 1513573187112042448ULL,  687416080475161159ULL,  484496930861389501ULL, // 71
 1625256440396143907ULL, 7358388240824901288ULL, 6055730836615196283ULL, 5897962221937294789ULL,  862205218853780339ULL, 4798091009445823173ULL,  644772714391937867ULL, 4255852691293155171ULL, // 79
 5287931004512034672ULL,  479051048987854372ULL, 9223312736680112286ULL, 8208392001457969628ULL, 9203071384420047828ULL, 8029313043584389618ULL,   38384068872053008ULL, 5477688516749455419ULL, // 87
 1504622508868036557ULL, 8421184723110053200ULL, 3312070181890020423ULL, 5344298403762143580ULL, 6340030040222269807ULL, 4895839553118470425ULL, 2806627376195262363ULL, 5321619225005368821ULL, // 95
 6897323351052656353ULL,  326700202259382556ULL, 7685269066741890339ULL, 8054506481558450217ULL, 9033685357580072100ULL, 8332083840200111891ULL, 6150885428026550986ULL, 1512337898865546216ULL, // 103
 8199105040814372402ULL, 5992489245523044576ULL, 5805925491165912141ULL, 6462078588740901428ULL, 3032432986636119647ULL,  684014216587805303ULL, 2062866308266478539ULL, 4710246706683903237ULL, // 111
 2582931674436654214ULL, 6634081669047384619ULL, 4348667075805862170ULL, 8709797118630931106ULL, 3102291567331830896ULL, 4007677779686056819ULL, 3181537205216282884ULL, 7685312895398193619ULL, // 119
 6230166267967393940ULL, 4445073392878012847ULL, 6567845718644358384ULL, 5735303218959420062ULL, 3818326047621250866ULL, 6215967033404567881ULL, 3201578835990656386ULL, 5618009974057121193ULL, // 127
 6739788610029497456ULL, 6829339210456112050ULL, 8493935726443239977ULL, 6024064041216774984ULL, 4910901177353758730ULL, 2402660215423901141ULL, 6328385469042109976ULL, 1026336552743661636ULL, // 135
 5319031175886297691ULL, 6147899420285774734ULL, 7155189892533296599ULL, 3040411528249066139ULL, 9079148035790160706ULL, 7631336259187501062ULL, 1735848228032553523ULL, 8841865345353351885ULL, // 143
 7054693804787060100ULL, 1117348452335342637ULL, 3540224776479663316ULL, 8698112751295819335ULL, 7949782284042624562ULL, 7320192297401204204ULL, 2742001999537296324ULL, 8389975416384686838ULL, // 151
 4594566761059248163ULL, 1501165996244698476ULL, 7974333404353588402ULL, 4276528517890056964ULL, 4574584047145139180ULL, 1664092205655206073ULL, 6710466936612628666ULL, 5562697082827418819ULL, // 159
 7730418033108470277ULL, 1643674162065661420ULL, 4598085991860103271ULL, 1275024689712004023ULL, 2995815802076682320ULL, 8379291955277910755ULL, 7718373802550781907ULL, 4575478933740345908ULL, // 167
 3637026097768731742ULL, 5615953139198055922ULL, 1394850415476549544ULL,  994724829554258181ULL, 3353602360456119297ULL, 3056494707387056564ULL, 3941402549363246404ULL, 5382485966906368762ULL, // 175
 6075865286374977385ULL, 4495719316202815011ULL, 8144575003331251482ULL, 4775075482575740521ULL, 5142588962615702398ULL, 7654836563724685694ULL, 2253518698951921445ULL, 6727159255066962760ULL, // 183
 9083588392742783827ULL, 8278532257693230228ULL, 3788849977643579953ULL, 7224501238281213584ULL, 2708702085602176855ULL, 7983149602608638702ULL,  453443660025710268ULL, 9098553180582364133ULL, // 191
 1945051622630002383ULL, 7979888192075959797ULL,  918272431137930210ULL, 2783273353364668755ULL, 7462587040943283626ULL,  475080085210565298ULL, 4221681342992318085ULL, 6383278501908566100ULL, // 199
 1098607658685511477ULL, 5336964468097400020ULL, 5488323779582184066ULL, 2806537946163949464ULL, 4395717578337332136ULL, 5623758465442492021ULL, 5708579044578044016ULL, 2155098154351405194ULL, // 207
  646468027950740578ULL, 8519885256314524457ULL, 4443205945222030046ULL, 7625601854989787045ULL, 3294524455206479694ULL, 3175154660940901721ULL, 6079549241475620945ULL, 2374731455929380780ULL, // 215
 5773499850889196181ULL, 2842242506077898988ULL, 1826417556695842788ULL, 1012105424093673201ULL, 7215095959864693516ULL, 1847924342983892465ULL, 2911431457556502464ULL, 2130561597941232315ULL, // 223
 4914636802612919548ULL, 5122639946743397478ULL, 3506861388077914721ULL, 2816891664585678947ULL, 2402179672518952546ULL, 5094219600333449091ULL, 6327107451521272681ULL, 6436513783743381050ULL, // 231
 5957274941287351215ULL, 4915686859172297494ULL, 5704164703060869036ULL, 4782455598309076767ULL, 3340284131652392813ULL, 7396191593658748468ULL, 1410030397478523789ULL,  586243035713878863ULL, // 239
 1730455969998702292ULL, 6459137915366584419ULL,   10380716923360193ULL, 2815331164506235620ULL, 6044703868624068227ULL, 1670917268729594072ULL, 6155129784247738774ULL, 6025674542403807212ULL, // 247
 8162815303291995705ULL, 1449353147661248728ULL, 7645781643692332298ULL, 8339496595568875677ULL, 3638816652556002569ULL, 8014409323403877285ULL, 6815697304970569665ULL, 2150142217566161183ULL, // 255
 5086163311162707626ULL, 4560098591896145866ULL, 8661937676030233161ULL, 7509104415380896912ULL, 6061608486534774038ULL, 8631708784647639738ULL, 8064080701876173946ULL, 5882398918313083890ULL, // 263
 7152000657065483688ULL, 2423759903104190617ULL, 4340188775089882306ULL, 7337104002392989482ULL, 8052200612043655176ULL, 3804480447268086369ULL, 5505421611205071299ULL, 4967307111831494238ULL, // 271
 5340530758764733699ULL, 6464756909304103642ULL, 7679463425422729431ULL, 1038993864589973529ULL, 4707138939380907218ULL, 7511066102588013721ULL, 5881341900432024953ULL, 1327999538008407040ULL, // 279
 2278473013165878614ULL,  161008747690997204ULL, 5291643905078371793ULL, 5374295181194353636ULL, 4402881997876334541ULL,  541626321424440739ULL, 5910026256441911750ULL, 2053144455592149503ULL, // 287
 5812967108718733866ULL, 6806281374144577045ULL, 4045018622314153027ULL, 8786758372389415150ULL, 8292605848969904386ULL, 3076633127095106145ULL, 2021173385314199059ULL, 8760546233189886366ULL, // 295
 8156392112658561788ULL, 1694936147733579137ULL, 7196295689815127153ULL, 8345136459001925286ULL, 7024634922683080619ULL, 3060737220915832271ULL, 5172324185417459787ULL, 5738474116327118906ULL, // 303
 4408411010991910055ULL, 6030977750273138038ULL, 1943286653349211262ULL, 7982215153851380223ULL, 3445444484928170987ULL, 5963096178011493373ULL, 6240108911342707395ULL,  542892229720188263ULL, // 311
 5198453314077744397ULL,  174420929026391692ULL,   83687671674408014ULL, 5547182613579814333ULL, 8182948135894874492ULL, 1596239697625445738ULL, 4498429480591303515ULL, 5893819537444009020ULL, // 319
 1432725232862192628ULL, 8136898083739533549ULL, 8295789334522664982ULL, 4388532351675743731ULL, 8731217442680364877ULL, 7984479650690946560ULL, 6628526865031581579ULL, 1697711267460014031ULL, // 327
 1541828221010126416ULL, 5774985104997678615ULL, 1168317549807430542ULL, 8733838484894539416ULL, 1483343483658555233ULL, 4259793933305087697ULL, 8441419966060224935ULL, 5665241414683329214ULL, // 335
 3631666682609208511ULL, 4026785050426529294ULL, 2251136625449449112ULL, 5221945762873157846ULL,  320201860227442162ULL, 7506936350590818294ULL, 3287053222413171262ULL,  328964830658798102ULL, // 343
 1853407779829945889ULL, 6454397336107832109ULL, 8202745623821644802ULL, 3149618978484905657ULL, 7071569934107772361ULL, 6444490032727799327ULL, 8339654341389346967ULL, 6940391027528346892ULL, // 351
 7465126869976956041ULL, 5452032971715844651ULL,  935749408495081243ULL, 2251873485551700231ULL, 5433660076591038936ULL, 8204680000423998091ULL,  516713386926250178ULL, 4326222705572732068ULL, // 359
 5414222729884497103ULL, 5391846496393572498ULL, 7522111793268351384ULL, 4856313385329306677ULL, 6727506347666212053ULL, 2436555516979793617ULL, 4963790787463715635ULL, 8591737641492046530ULL, // 367
 1897378546605981431ULL, 3698437077010041566ULL, 6271005278382309359ULL, 4089079230266037024ULL, 6485748368291935458ULL, 1978634582415490525ULL, 2380659983768312397ULL,  149210880824638600ULL, // 375
 7862105294961494611ULL, 2965106995796883438ULL, 4859150813094429798ULL, 2307782702894158668ULL,  675479725473744505ULL, 8207073778254132904ULL, 4897912725379833339ULL, 8844816137818323304ULL, // 383
 3172465924537226840ULL,  405047190232101638ULL,   46819710123005995ULL, 2701392482035849230ULL, 7564513612185914322ULL, 4311657792483383986ULL, 1761512319879753836ULL, 8516684277047227707ULL, // 391
  778554013671457876ULL, 6561090629361542827ULL,  856467582408233294ULL, 8000989950671753718ULL, 4389839513127394326ULL, 7171217825114405235ULL, 5336759035960254984ULL, 6859671469343299332ULL, // 399
  889171069344249634ULL, 8729324122267274919ULL, 2535473045366247473ULL, 7468558853587229787ULL, 6887371636194655392ULL, 1598416186239287842ULL, 7017713284671344199ULL, 9049129531913398221ULL, // 407
 3150147660273591431ULL, 4210600086106430294ULL, 6032349415526123632ULL, 5538562552711286172ULL,  749537652992259562ULL, 1263197089156226712ULL, 1055698230194092523ULL, 5372149612595220563ULL, // 415
 6164215185515118503ULL, 2880860079005597786ULL, 7085446271898518960ULL,  352930816871459803ULL, 3682891507101373378ULL, 4174957788310548317ULL, 2843075425247520090ULL,   50128016405968037ULL, // 423
 1164191370934560163ULL,  776466295643127735ULL, 7248946104583290183ULL, 8395357680406909594ULL,  578065150323070051ULL, 4861408413968255779ULL, 8558051289060402894ULL, 3578632680055504731ULL, // 431
 5888287692011387505ULL, 4975210633894819405ULL, 7585539659094121579ULL, 8499807796146045553ULL, 7279488453877026853ULL, 3522291886406144567ULL, 7452108833118472441ULL, 6892414929938366306ULL, // 439
 7833148007471994583ULL, 6589468951511456944ULL, 4760538032786164845ULL, 4633833800216250191ULL, 6196637325624467580ULL, 6972366565773881119ULL, 1282056164890947049ULL, 1806838982991031744ULL, // 447
 7787119968035712561ULL, 1697333749250173051ULL, 2886819026502387254ULL, 8194346719615777482ULL, 4425163058290744508ULL, 1842127287941893083ULL, 6065686471979258846ULL, 2046828019605214290ULL, // 455
 7180051406606977623ULL, 1310812483089694420ULL, 5174379529325486156ULL, 8055820585647601557ULL, 6216516458488191127ULL, 7678961400220239890ULL, 7132442319246349616ULL, 5445544445574180571ULL, // 463
 7044477958947379680ULL, 2622105803847568893ULL, 8116647707660763715ULL, 1650860394267113073ULL, 4086347055775716810ULL, 5972338585798657205ULL, 3004157861087006090ULL, 5604123935644161118ULL, // 471
 7432091541813250569ULL, 3678054631230090918ULL, 3636210663037540695ULL, 5530743852379138845ULL, 8315318292442139888ULL, 8127927705902610542ULL, 4248761557806131458ULL, 2697206790553707905ULL, // 479
 2269606276886560416ULL, 2777792428493726456ULL, 6912393085304814663ULL, 4481320674641797091ULL, 7921640502822362038ULL, 2704029599420922809ULL,   26081796429741471ULL, 2663263557893800226ULL, // 487
 5999717916944163659ULL, 1617900333524693501ULL, 8851821366999324164ULL, 1041911625650400912ULL, 1911605369088626761ULL, 4944784158418142485ULL, 4296567409320250952ULL, 8230234406793493549ULL, // 495
 3737931512960802325ULL, 7729055629604392395ULL, 6213307619045800079ULL, 3202320667784080493ULL, 4217291495272059462ULL, 6614002414215462278ULL, 4991131763267827775ULL, 2478174590942533517ULL, // 503
 6395212120083410545ULL, 2180034184336660524ULL, 2021347077811250852ULL, 4744057031664904042ULL, 3168413102537813434ULL,  869947341234827321ULL, 8107460104347604757ULL, 4807782161210099946ULL, // 511
 1661464509605989260ULL, 4048972144011956103ULL, 6300470025646097508ULL, 3562976178957883489ULL, 3934271042146264092ULL, 5537762775765182096ULL, 1007500489425573008ULL, 1469508416211498981ULL, // 519
 2888640256467650472ULL, 4203002018587199351ULL, 6871488410535220941ULL, 8842939781178778939ULL,  189156162330631008ULL, 8281509985928839306ULL,  366324796732375515ULL, 1695263810277091233ULL, // 527
 7179385866391363626ULL,  679189395987894659ULL, 3772156729230308125ULL, 5550873339246066490ULL, 5195772129116864460ULL, 7408458539935888276ULL,  657829408009412584ULL, 4382613186901677918ULL, // 535
 3304137519840770954ULL, 8456456998755964382ULL, 8309302216738721207ULL, 1768783365444507359ULL, 8565539830786281613ULL, 7571702615335263118ULL, 4692841422655250653ULL, 1736281894854762449ULL, // 543
 5787830343046625879ULL, 6905339103079556503ULL, 6657636867935918905ULL, 8043042804651246766ULL, 5098104487922287259ULL, 8833309580887928673ULL, 5882724227024970684ULL,   79031523553987093ULL, // 551
 3354793901716415894ULL,  915743597089730974ULL, 7388141226387659532ULL, 1715810423814937701ULL, 3511448270610358246ULL, 6438801610983046658ULL,  107735391053003554ULL, 1629772908602671564ULL, // 559
 1367182761973174056ULL, 6232180767374303983ULL, 2544580386740750388ULL, 1431484551104841062ULL, 2056608801753391072ULL, 4175246729444994387ULL, 5033972826072824711ULL, 7902822736641843940ULL, // 567
 3566394734159189851ULL, 1606118766092375147ULL, 2279721255116070144ULL, 8461472946158722561ULL, 3386070192202737860ULL, 4772087186432228778ULL, 4628613989270026711ULL,  165999276205627744ULL, // 575
 5713600076304803545ULL, 4797244340002550624ULL, 2226659537600963565ULL, 6677493296558848477ULL, 7270150984097901965ULL, 2999229333425424234ULL, 5883646240000564889ULL, 2246146459955448370ULL, // 583
 1273874330089291473ULL, 1957832860997052508ULL, 7174194422397587310ULL,  121393080519465143ULL, 6872836294882959968ULL, 4830698161001290776ULL, 2071968327279302104ULL, 8273874998541411638ULL, // 591
 2171505443932074440ULL, 6820376825479916479ULL,  853104153794318684ULL, 8681433323034876291ULL, 5903866074333056205ULL, 1980634876500879359ULL, 4135970657112984380ULL, 2790809212636340570ULL, // 599
 8079046571094085839ULL, 8963440574555121118ULL, 5944575850376843283ULL, 7366761532234963055ULL, 4754941887318988023ULL, 5872118351408271019ULL, 7970785095735880192ULL, 5389106581327619970ULL, // 607
 8770368612636609656ULL, 5317083480051249534ULL, 7260609457284233438ULL, 8523355869615856831ULL, 7232435390131842031ULL, 6505243770093875473ULL, 5507400052160739055ULL, 7554878995444842808ULL, // 615
 4821323021656316962ULL, 1169571504034686971ULL, 7156409153512482219ULL, 5136566937140960937ULL, 2287048657943835890ULL,  291517181720208755ULL, 6707934564789362999ULL, 1953380217490635451ULL, // 623
 8666735133000589366ULL, 6655031872294833028ULL, 2822236429065942843ULL, 1421704007042817727ULL, 7235634416465358081ULL, 2976333790585576021ULL, 7999628725159617084ULL, 7882737016023886767ULL, // 631
 8602788288763282083ULL, 5140106545139542675ULL, 8365269521620931605ULL,     432370395423474ULL, 2838614697120183954ULL, 2463407857387448314ULL, 5972573315163460954ULL, 6578108367773451640ULL, // 639
 2463879733417709295ULL, 2896536927884545701ULL,  741411871414647104ULL, 6117415946974144853ULL, 3021816679504248117ULL, 2273336682796550707ULL, 1178218454175555384ULL, 5395653073475280335ULL, // 647
  761638147316943245ULL, 7093460107210082859ULL, 2365689029333258655ULL, 1332481774793090730ULL, 7385842027573654914ULL, 5527480953655697402ULL, 8212677704911139162ULL,  327607680336838764ULL, // 655
 6891985487787882096ULL, 6739301566105208436ULL, 7542385541001264246ULL, 6387071610227758578ULL, 3503723181224489845ULL, 3138903547164858652ULL,  369737918135195144ULL, 5239576337189139593ULL, // 663
  623572167692894029ULL, 1034911695387753784ULL,  980184848295177169ULL, 8193564925627078942ULL, 6163283100213899911ULL, 3277698147043879983ULL, 7379891127002373772ULL, 6605774171891819563ULL, // 671
 6829450433454619565ULL, 3458529902430717100ULL, 7755049175219346025ULL, 6489294121251844558ULL,   59265729825749700ULL, 6717341950694137996ULL, 8939382254349550037ULL, 1560379713413083234ULL, // 679
 5843210660720432074ULL, 3328843584361304592ULL, 4962684881129165181ULL, 5966050345882181871ULL, 6796710313414124615ULL, 7055184714906036198ULL, 3625682281304521146ULL,  778361946789910479ULL, // 687
 8559290551085332145ULL, 6380224617652956555ULL, 4859121327171811099ULL, 9126368011186446073ULL, 4050972331464469060ULL, 5347390711400956588ULL,  130512143494501530ULL, 4106564940589362493ULL, // 695
  279689801055068328ULL, 3573746274228283392ULL,  511072959082015355ULL, 7144970633114973739ULL,  336801041474459149ULL, 3037640639203086742ULL,  190998124254538275ULL, 5194244002830828848ULL, // 703
 8052894441656075746ULL, 6617884325787513326ULL, 5997243281384067605ULL, 8607030791118155484ULL, 3917846190437699692ULL, 4591826124953004148ULL, 2415447857918567574ULL,  798709096997391723ULL, // 711
 6910427553638257918ULL, 7937512341157869413ULL, 4688879952333880922ULL, 5505911748361637436ULL, 1612522211729525665ULL, 8988164316587320368ULL, 3136182938850429241ULL, 1330436970174191256ULL, // 719
 7310132861897415707ULL, 5654349077772323864ULL, 5245829561373596014ULL, 4908847678125501067ULL,  545685262992747645ULL, 3988662044593753826ULL, 8975692831766096048ULL, 5656270775589983826ULL, // 727
 9159826510669337017ULL, 4860876822267591975ULL, 1006149978308885319ULL,  427643383102006395ULL,  463596884484401975ULL, 4422192521727507629ULL, 5151471943250440715ULL, 5565485169134044043ULL, // 735
 4477578753156111309ULL, 7322236868277337176ULL, 7034470039939811991ULL,  440339990483967766ULL, 3285014275771791842ULL, 1317916384841615400ULL, 9216373174521383494ULL,  476711384525398080ULL, // 743
 2121226207764868146ULL, 4554790033334643730ULL, 6481004740567443659ULL, 5746048378259648098ULL, 5174869077123717433ULL, 1321009413679384690ULL, 6697498357181562454ULL, 4341201747517495660ULL, // 751
 8882956790717537184ULL, 2451741349010345822ULL, 5447779090635603111ULL, 5050838064175324492ULL, 7321083370277067885ULL, 2546756402383214875ULL, 4119569572593763311ULL, 7243540115129877170ULL, // 759
 8361055995849086658ULL,  144799931725092762ULL, 7557391530193878867ULL, 3339918289906307984ULL, 6835717168822153485ULL, 4611857556129686481ULL, 2324050249544345600ULL, 6261548558336870790ULL, // 767
 2169753850027430657ULL, 8677689795062196697ULL, 2381999205691787097ULL, 7126954265920685617ULL, 1650538232397425818ULL, 7793795042762787450ULL, 3473806422652704935ULL, 2787531550642528426ULL, // 775
 8388921232647633906ULL, 8230179079061286648ULL, 8823179788057394753ULL, 1008457257447298001ULL, 7007653033551027851ULL, 1521996372318936753ULL, 5350002082516874464ULL, 2091966245352737325ULL, // 783
 7273462803295731996ULL, 5913916829910112138ULL, 6051439823795419947ULL,  911800513394306108ULL, 4267837694720113928ULL, 4248713828624226382ULL, 5296186640340206564ULL, 1129762457870091546ULL, // 791
  745204820484632893ULL, 1961304520970058523ULL, 2483294832189421210ULL, 6780537489564540621ULL, 8590076594141824655ULL,  375907075126270898ULL, 6862706759979476406ULL, 3013090529051001682ULL, // 799
 4014157328334133733ULL, 5344887496405692231ULL, 3521134381082359960ULL, 8544203173615107286ULL, 5738911529102316091ULL, 6307244154173033297ULL, 1382418303501569565ULL, 6273461964425844213ULL, // 807
 7573576118562178173ULL, 2472635693525970648ULL, 1981156224810999804ULL, 1101074742782496829ULL, 8332335012414180132ULL, 6064567417607004668ULL, 3944855144830226894ULL, 1661095225104537516ULL, // 815
 8781293266616860714ULL, 8801237581996687556ULL, 4039298696602935927ULL, 1644655651939626596ULL, 2468241642991833790ULL, 2366564317143255761ULL, 6165534385595976224ULL, 5978283066184638517ULL, // 823
 7651420730110226902ULL, 5349237379052718516ULL, 8480719910241311923ULL, 1757065702311983199ULL, 7927293944038950369ULL, 4337980582337337521ULL, 7675919029722218409ULL, 1384417481881535331ULL, // 831
 3781686487802361681ULL, 1089523833473972374ULL, 9084351745780466113ULL, 8375823368960806523ULL, 1462707256818966703ULL, 6179881298410927451ULL,  935669891816126995ULL, 2920608072863545708ULL, // 839
 2162339052744107167ULL, 8996295539992804796ULL, 5496785534749220115ULL, 9009369807636392234ULL,  128250284219256950ULL, 6849484493947796132ULL,  899682121558569529ULL, 5814637536571002867ULL, // 847
 9196185007147745839ULL, 3278981759058936658ULL,  414968818603798404ULL, 2163014031136184433ULL, 3950448742561737498ULL,  282545678835448579ULL, 2054315624728093533ULL, 4249837219449442582ULL, // 855
 2249627162465515408ULL, 5636341603602843983ULL, 5552749925890000110ULL, 2723748108735805336ULL,  322945690648638548ULL, 4261797487195956612ULL, 8583762539510673476ULL, 5903996423715622935ULL, // 863
 7757224359104642561ULL, 8390368191169787493ULL, 2391039239232234807ULL,  826497214128946616ULL,  449533478143532194ULL, 2004234579317060990ULL, 4312196644663389483ULL, 6720503782491310076ULL, // 871
 1053460486646682984ULL, 5084864469636348255ULL, 8555812719328871364ULL, 3063838592233615291ULL, 8158473144200979251ULL,  878014187477425830ULL, 8178699068489239223ULL, 6852067121953228268ULL, // 879
 6741616754965348904ULL, 5661372527297803837ULL, 7349073457424468775ULL, 6250771941284263857ULL, 7596912630096178353ULL, 1079084003732334537ULL, 5285706284660536260ULL,   24189008178921112ULL, // 887
 1709689094313279761ULL, 3722005151284093827ULL, 3694294019332647150ULL,  697516149910109423ULL, 4888107781797537918ULL,  924886732385984409ULL, 8357540948580584019ULL, 1332614163021364206ULL, // 895
 4572645089457709526ULL, 5785069624033965019ULL, 4258484388448691746ULL, 1273581413035594951ULL, 1844104007915034811ULL, 5317762219594886320ULL,  928881168284281942ULL, 4245605031322981804ULL, // 903
 1227632668734300991ULL, 3680700039384937022ULL, 5530081887122525294ULL, 7551321808303347790ULL, 5953746528830065346ULL, 5038252447644772386ULL, 7029790360321252717ULL, 1740329068244771217ULL, // 911
 4141481264130528829ULL, 5077409922951588929ULL, 1114496181739929848ULL, 1808618597414539058ULL, 8703656754902597017ULL,  865038445375759924ULL, 3244960007928457002ULL, 3047736144634697559ULL, // 919
 3854881622451041552ULL,  171147321432479382ULL, 1883280342902356162ULL, 1356409106931562090ULL, 6975305637865350861ULL, 3701570273286035611ULL, 3542156124092727966ULL, 7160787369961046910ULL, // 927
 3743925994807283609ULL, 6860231003947701562ULL,  142444555190268104ULL, 7817022364054694469ULL, 6571858383664373839ULL,   31895153127741521ULL, 4569332251421903962ULL, 5066039031400813027ULL, // 935
  584695451369748798ULL, 8585805346591736552ULL, 3736283447861827422ULL, 1081630622707299717ULL, 7113503966949890015ULL, 6269941005909262950ULL, 1001728198521882701ULL, 9115925442411098968ULL, // 943
 7222181599368361380ULL,  380704330874120311ULL, 6198261976158973183ULL, 6987355425649235150ULL, 7656415471799460662ULL, 4140194675559142599ULL,  875509843979607240ULL, 2203217523384758522ULL, // 951
 5220048027233439524ULL, 3928181085326493702ULL, 2284493251937725749ULL, 1221176489260377262ULL,  569640569319836588ULL, 1606913240515649426ULL, 2475101799477882104ULL, 6317022961170885599ULL, // 959
 8252251057723480957ULL, 7838537516550097162ULL, 5672081954414012180ULL, 8773889313553798602ULL, 3398399445119273720ULL, 7107501071430318555ULL, 3673573626658312508ULL, 5734114584448236998ULL, // 967
 1652997397524471480ULL, 8626581092132243170ULL, 5448735343101231960ULL, 4112115833642520833ULL, 8115503044002452132ULL, 7589744680262787838ULL, 7218495722377626494ULL, 1841144170764509754ULL, // 975
 2157750866211578677ULL, 2251143699124266871ULL, 6058830551509420316ULL, 2711586168834544787ULL, 5492372928081455058ULL, 4507767251020282836ULL,  683061763517872452ULL, 8836196171776743790ULL, // 983
 1457433433681182567ULL, 6273549814799508457ULL, 8863790773739539425ULL, 3701172650201223620ULL, 6881322685745423742ULL, 9123154589660257827ULL, 6750940904630584225ULL, 1900449075512346615ULL, // 991
 2197236369734855585ULL, 7515152554612977951ULL, 5953253744017452207ULL, 8489924878870710482ULL, 1599081887855350817ULL, 2164829157424090512ULL, 4792829893797445185ULL, 4618202816710534497ULL, // 999
  793686488987944783ULL, 3933060063111299175ULL, 2830674206242520628ULL, 8190027008907407799ULL,  478405972214466287ULL, 5365071224253959342ULL,  607364246280622135ULL, 6914666608684953958ULL, // 1007
 2193741031105692691ULL, 1837295498257494165ULL, 6209813808740935735ULL, 1145877377807467844ULL, 4878168433309646350ULL,  867667317557184957ULL, 5088359834020067794ULL, 6697889615583459831ULL, // 1015
 7154250728922986600ULL, 6316151546733237331ULL, 9041810357299989642ULL, 1250177749148932687ULL, 4149244043643983332ULL, 7526191169504730633ULL, 4657397232019454883ULL, 7561208901645115891ULL, // 1023
 1200560830923289076ULL, 5774760999246033017ULL, 1278980703321263088ULL, 5995898303700702852ULL, 1007972879725250705ULL, 6604775429030708813ULL, 3126063720818315104ULL, 2755006995603587974ULL, // 1031
 5486870651746859682ULL, 1818495309049773670ULL, 5130593028562886115ULL, 5602153258409302694ULL,  460549992599338931ULL, 4813073325276699106ULL, 9122458134541649951ULL, 2745713446594198286ULL, // 1039
 3326042553114873437ULL, 8510021568274388032ULL, 6217740786038956357ULL, 1538800351917302859ULL, 2922741421670910726ULL, 4098674338359782458ULL, 2999496751852628700ULL, 7105747553228268080ULL, // 1047
 6701467843740387225ULL, 4568304332494335148ULL, 2769543879327005003ULL, 2665153866505623875ULL, 4852057949403086850ULL, 8348041094397654102ULL, 1405765344994586362ULL, 5850790973552640566ULL, // 1055
 1167484915270015723ULL,  113459113395853221ULL, 1196616303237792058ULL, 5387567330218403335ULL,  572463207258908297ULL,  944790830543152808ULL, 7116550967834264066ULL, 2834955321561282277ULL, // 1063
 7751409209194686830ULL, 7203335603725922072ULL, 8350345205956995811ULL, 4527674925740743608ULL, 8123344627306576769ULL, 8730175161300300552ULL, 5522726489568182130ULL, 5037545831408363475ULL, // 1071
 1271662568263125940ULL, 4852065069292394126ULL, 6803264403674921834ULL, 6587636598557104431ULL, 1279129992231947991ULL, 1724315533190591321ULL, 6359593780311869615ULL, 3766955691488860788ULL, // 1079
 2739158467657747919ULL, 6185212004318696663ULL, 2392036693884260840ULL, 5845162757412758425ULL, 5141858882930737310ULL, 1597747217634965476ULL, 1486187947296639967ULL, 8131424740482341486ULL, // 1087
 2562925952697802545ULL, 5226129387060683905ULL, 4776378133428497810ULL, 7518545934746745998ULL,  899449341008493960ULL, 5227817048871882050ULL, 4578760285834435110ULL, 2923302039264852053ULL, // 1095
 1518319964013457731ULL, 9184050392399634601ULL, 1374656902080921020ULL, 5202365940086296724ULL, 1934434966551059171ULL, 7957729120655801962ULL, 4212034167762331697ULL, 6178473429407465045ULL, // 1103
 1402527558201067990ULL, 6917778437830599165ULL, 4771624726228902023ULL, 3011041778287752146ULL, 5232441766805130867ULL, 3706745153850467400ULL, 8010259530665601227ULL, 7905748762834522256ULL, // 1111
 6515189201991576010ULL, 4215564111427034426ULL, 4448896200924673403ULL, 5182989852229379552ULL, 6994671168084850248ULL,  580582040173688608ULL, 1559756721311513891ULL, 8758293415157573083ULL, // 1119
 8940286247047043147ULL, 9141189968994664034ULL, 2442280115001189987ULL,  936240973246240483ULL, 1944346500732498760ULL, 8262551891148660081ULL, 2049661285504735176ULL, 1036441448072640035ULL, // 1127
 5587983702947979066ULL, 7231324548271581464ULL, 5446563567715778860ULL, 7196839032346125587ULL, 7108289297529107267ULL, 5201195995790775789ULL, 5313104507393675688ULL, 2406958257203459936ULL, // 1135
 1965445149077226400ULL,  295185621447303878ULL, 5253635899770988534ULL, 2859075106882477787ULL, 5874412717495284948ULL, 7929216392899327826ULL, 8843183582599735885ULL, 7265552449346588207ULL, // 1143
 4994291357174415571ULL, 6021303115710815804ULL, 8464447326557062720ULL, 4435345584833788276ULL, 2548819149014687618ULL, 5794038569217239530ULL, 5149286913568394026ULL, 3668570343581981469ULL, // 1151
 1302400978909271820ULL, 2299085292016744654ULL, 5195182555427862413ULL, 4530647240181488192ULL, 7056415360075584501ULL,  546925204361099519ULL, 2978777396048264968ULL, 2660650113363740617ULL, // 1159
 3862610579763789430ULL, 9190551636963131867ULL, 3453351305569429844ULL,  229678424137662010ULL, 4815694724416965296ULL, 4640722076285188608ULL, 5001341782920825198ULL, 7856341663776203941ULL, // 1167
 3049676343746712322ULL, 3636407605803065212ULL, 6090215313542427933ULL,  867710100535654129ULL, 2180174405355817808ULL, 1376113501434038101ULL,    3740917454698271ULL, 3908648517771987508ULL, // 1175
 3495344807017559332ULL, 6970037370979531340ULL, 8278353304969971550ULL, 3727494532463814479ULL, 4000060747322351787ULL, 4612285593662744553ULL, 7454136993908881005ULL, 6081773257365981844ULL, // 1183
 4177310133079894529ULL,  301928165268100095ULL, 8661863672298824654ULL, 4967412046530783281ULL, 2584273568553024225ULL, 6777617848646400374ULL, 1156917130202791588ULL, 6454365983226210197ULL, // 1191
 5338722449591439289ULL, 2377586015100047937ULL, 2177375071318415977ULL, 8264379714533763366ULL, 5249925117310606047ULL, 5955466314176652590ULL, 6898548489778421149ULL, 4761131377313012412ULL, // 1199
 3308676358854646228ULL, 2896639997918570173ULL, 6232697808384866732ULL, 4365834043688496320ULL, 4984205562001849972ULL, 2181613821795870349ULL, 3382974182896249313ULL, 1570012592570216673ULL, // 1207
 3613639085518270468ULL, 3892028317634515122ULL,  829307114084383922ULL, 2745077942917645698ULL, 6586329262360267495ULL,  336550271052409054ULL, 2291039752779897459ULL, 6113992303434936354ULL, // 1215
  937369154091758166ULL, 8346884108080722409ULL, 7651312311095567821ULL, 6763666296117289103ULL, 5409425966099596512ULL,  329896491592507738ULL, 8357887890375431487ULL, 8290724746776242267ULL, // 1223
 5847507689685505373ULL, 8539169098023096241ULL, 5892417018574516965ULL, 3532675004752554400ULL, 1538047220030521315ULL, 7516879959363921488ULL, 8966906926317868570ULL,  205431047590186654ULL, // 1231
 4194760488295329106ULL, 7850971003883992179ULL, 2818289233730576177ULL, 6034846600926246753ULL, 5113173346352372767ULL, 7796743309823759058ULL, 8264652178828962550ULL, 6995844141059438241ULL, // 1239
  600105008298947643ULL, 2342230600722289250ULL, 8372516206313724805ULL,  524524234098697453ULL,  520758846572514946ULL, 4516278362299889088ULL, 3225532380404441521ULL,  945197775295491340ULL, // 1247
 4050652528706208998ULL,  819621594381115939ULL, 4964062007618696834ULL, 5873284923264698409ULL, 3995839253118825024ULL, 5101552516989322239ULL, 2087380181271615018ULL, 7925907222457736586ULL, // 1255
 9185665819126776051ULL, 9180007218591510918ULL, 6919671391800093680ULL, 9022001380222679009ULL, 8522563607150567858ULL, 7704723970113249038ULL, 9036617115557868032ULL,  721644778250261094ULL, // 1263
 8222718487733448090ULL, 1509467330843826942ULL, 8395734572233707023ULL, 4817271775613662909ULL, 2606036411339947556ULL, 6205321179295800710ULL, 3569476874794710364ULL, 7380901784329608883ULL, // 1271
 5952622153371495166ULL, 2643208610945143496ULL, 7818696377606809262ULL, 1865979711982129504ULL, 6756745655685871691ULL,  419239859600575427ULL, 8997253394944310408ULL, 1210516300648522033ULL, // 1279
 2682151010482213555ULL, 2736636269613059646ULL,  879363846598614872ULL, 5022715330063933714ULL, 8249360298827448247ULL, 8178816852697608650ULL, 6912520839551203753ULL, 6127235791686609763ULL, // 1287
 4450511527236526263ULL, 7290692464384736149ULL, 1988910317942540501ULL,  940351776888901573ULL,  280631789047659875ULL, 6092274666867633003ULL, 2500476274340313522ULL, 8051112992960177166ULL, // 1295
  799402562153728204ULL, 7037140830683671848ULL, 9118285268797699912ULL, 5164166673133356448ULL, 4841148598545272018ULL, 1516366628535495700ULL, 1232586054441338856ULL, 6172068353014655779ULL, // 1303
 7190674788146566563ULL, 8728933449666424837ULL, 4172688924351673262ULL, 8701869042862743448ULL, 1805504824042543955ULL, 4507833860536527614ULL, 3650190609979430815ULL,  265236342055641450ULL, // 1311
 4899952044507873625ULL, 6128359583032985744ULL,  915489261924850892ULL, 3715766772513877922ULL, 6188765708287755675ULL, 8286935259564339227ULL, 3652363786564186925ULL, 3881077301109732899ULL, // 1319
  251648319414059511ULL, 1575879611385276232ULL, 3832551901474448882ULL, 8877657957165065912ULL, 6625148292416328163ULL,  720665782750107210ULL, 7497694597488746690ULL, 5501560039821625839ULL, // 1327
 8288279299692545607ULL, 7969139879445158590ULL, 4475701805311402160ULL, 5737034383085259955ULL, 7693668016153634326ULL, 8862447235178509263ULL,  812857140369299468ULL, 3742326303719023124ULL, // 1335
 6906791215502331930ULL, 5488842705696575402ULL, 6372582534645026877ULL, 7154027803491514194ULL,   81876372146391064ULL, 4826325657895046051ULL, 8860595708899886418ULL, 1530473535774722806ULL, // 1343
 3511061242566764562ULL, 7905899496500276909ULL, 2737775991321882644ULL,  204486485620289294ULL, 9220159446378100782ULL, 3330731736483786606ULL, 3363714187672456400ULL, 1874150013970950719ULL, // 1351
 3167891922747300574ULL, 2563104442147050232ULL, 3282749310967099467ULL, 4091461206449163580ULL, 8368453795025410023ULL, 1720824618041336125ULL,  798928484056362610ULL, 6707808404100884691ULL, // 1359
 3527539534328648168ULL, 3073380741941485382ULL,  586525669622371041ULL, 7473387496271271975ULL, 3121428913653281075ULL, 1392957629038320458ULL, 8653805236103092503ULL, 7532276463350782702ULL, // 1367
 1406728327969505138ULL, 2915427538238201617ULL, 1365769077426845745ULL, 8054103324197578784ULL, 6701303572176799021ULL, 8516528302668000594ULL, 3802854063495165330ULL, 2586849754591447587ULL, // 1375
 2167928492510752165ULL, 4372337082324601207ULL, 8938097724094707646ULL, 3337767241278819222ULL, 4203099737641380148ULL,   97925667511658229ULL, 7997832515473894506ULL, 6231858058885314114ULL, // 1383
 8502211003800465354ULL, 4870666443377744794ULL, 6930802311398556065ULL, 1155458877822531603ULL, 4252953642547137816ULL, 2685593870393932397ULL, 6449579809254898570ULL, 6162829264863857189ULL, // 1391
 1709302082516053497ULL, 2148590427043998134ULL, 3934146854222263611ULL, 4260182374944165545ULL,  993710503932664877ULL, 2547407494046048444ULL, 2764938142905939842ULL, 9172731821700215923ULL, // 1399
 8703179119642553425ULL, 2688385152076681031ULL, 8521423963238699976ULL, 1595971201904653504ULL, 4292459173534969024ULL, 2383441235971105675ULL,  330636660429190077ULL,  912803215140934010ULL, // 1407
  634692774313869644ULL, 3463966514848712559ULL, 8547751314802716797ULL, 3482714179250033912ULL, 2858884895393926071ULL,   86260760137422145ULL, 5586015193667636402ULL, 7667600146004011653ULL, // 1415
 4855646771058563522ULL, 2253059631639488246ULL, 4976457291125129510ULL, 7704704268521033323ULL, 8130595905842727652ULL, 1564211380182865457ULL,  187671933765033894ULL, 1277799272362385496ULL, // 1423
 5538408235361247964ULL, 5391204334467553146ULL, 3242542642296684000ULL, 5180877290894827524ULL, 5680668156601344550ULL, 2501878536988216528ULL, 5302758591720144635ULL, 7109133587722135516ULL, // 1431
 2078719903068401953ULL, 5088732031956354632ULL, 3987852013903506056ULL, 7100721628441305134ULL, 4434837735554942633ULL, 2132936418751050766ULL, 1918575562798226954ULL, 5444874379546363713ULL, // 1439
 8152501480472017966ULL, 3096399274613888065ULL, 1263253160464403246ULL, 8273099619309568933ULL, 4321042579686189451ULL, 8987232626184985645ULL, 2497712763432978378ULL, 1335462464770457924ULL, // 1447
 7011815359559193307ULL, 2408237830282586930ULL,  770886723494648895ULL, 4671371221646865104ULL, 8950520428345803199ULL,  604862091514792247ULL,  991671296804059973ULL, 9102707750301245617ULL, // 1455
 7662443152515264308ULL, 2092472824187744641ULL, 2029639516714297655ULL, 6646245588895672248ULL, 2693806526085547419ULL, 6751111230952045385ULL, 4059728318423451631ULL,  544579919165130320ULL, // 1463
 5287396155594540057ULL, 3624466973440825390ULL, 3238405171316833507ULL, 2040635303431488320ULL, 5876773798630830557ULL, 4611277512802147948ULL, 8695233868154920176ULL, 6789245833708709013ULL, // 1471
 7466348214308975631ULL, 6836629255645333127ULL,  800547025536731964ULL, 6623297788421500938ULL, 1446236946909852197ULL, 8685872836845837884ULL, 3014238645681465313ULL, 7354136902166205662ULL, // 1479
 2959898470751393295ULL, 5136545647805385811ULL,  827698001280137228ULL, 9163857204876087700ULL,  599306307180895243ULL, 4349544858491082508ULL, 9042375909219561246ULL, 7205473124443931935ULL, // 1487
 1573765276386693560ULL, 7557967780842258549ULL, 9078233153068202470ULL, 5868665849250737612ULL, 9108930517075237842ULL, 6807063328456582687ULL, 5338247370545475733ULL, 1978059894618124206ULL, // 1495
 6693060036815235083ULL, 5273077452952770966ULL, 5068414452510641044ULL, 5001857796856596992ULL,  541953262795283243ULL, 5738888898172575898ULL, 2043449275985403054ULL, 7646309223981313400ULL, // 1503
 8539720335438672225ULL, 5991526852148038490ULL, 1715426461375520364ULL,  472307477920601939ULL, 7967987311638316335ULL, 4500782069645393394ULL, 2993826969732872304ULL, 3157636454066076776ULL, // 1511
 4370075465537284513ULL, 7984273001346252946ULL, 4420904486843187496ULL, 5882838640884686037ULL, 3890789381988461471ULL, 5323814889093506718ULL, 6119345490111701801ULL,  328081171343701683ULL, // 1519
  504285005186580995ULL, 4606903203492921298ULL, 8956428683740773172ULL, 3820696414600534701ULL, 3135209455230899351ULL, 2560534566998554151ULL, 5576948411654669887ULL, 6592551388214652291ULL, // 1527
 4925512889081219213ULL,  938769719382844694ULL, 9116211118349170857ULL, 5085903095150552586ULL, 9219963860322533210ULL,  494495082454461590ULL, 4933098023609327806ULL, 2328259067567765262ULL, // 1535
 7142184272994936151ULL, 7657094497505493808ULL, 2791000917766917637ULL, 5352912837255504111ULL, 1352525322642404989ULL, 2831874761106812837ULL, 4408246388463913382ULL, 7653125568191802525ULL, // 1543
 5554506469467786046ULL,  233432586202438634ULL, 6190131610987402142ULL,    7601973295294512ULL, 6505681624447307420ULL, 3079288717622293884ULL, 1324673305252952079ULL, 7652790644292735515ULL, // 1551
 3119338021543453547ULL, 6118726456979078643ULL, 8340931978047222568ULL, 2613177271158445070ULL,  938342624779089401ULL, 7399558993836959330ULL, 5646106146879430875ULL, 5456976260375810516ULL, // 1559
 5197835780188824754ULL, 7424586124012171265ULL, 1786372488928980914ULL, 8351318790924094280ULL, 7934285148762254583ULL, 1284089689870855592ULL, 7614783259029155152ULL, 8502443991113351790ULL, // 1567
 5800021397957301518ULL, 7421088178733236780ULL, 7646065664322494275ULL, 5387666600837116380ULL, 6255945447449647597ULL, 4707625271932261597ULL,  169794046138510141ULL, 4655920132671776483ULL, // 1575
 6631638339884061807ULL, 7532225178501302335ULL, 1065950278134378262ULL, 7486692903187071599ULL, 8867407404262233164ULL, 9035821841909580052ULL, 8484290888219258842ULL, 8769567863711994456ULL, // 1583
 4489320168403551203ULL,  755149551616757022ULL, 7778177420774845119ULL, 2273050050265561188ULL,  483297673418397496ULL, 7489430384549052277ULL, 7921904815503635442ULL, 6020721543736758884ULL, // 1591
 5779112698047741245ULL, 4524809908343704706ULL, 1766374583246614059ULL, 6621926361929009248ULL, 2335541330879151880ULL, 8669228574943200276ULL, 5525897924149710071ULL, 6657400433712903114ULL, // 1599
 5959336372683582192ULL, 3703859847274787842ULL, 4331994103076241379ULL,  101520546823625308ULL, 3734213185030879655ULL, 5468383496051546513ULL, 1289557372736471082ULL, 7762917084360144378ULL, // 1607
 6595307692611782297ULL, 4690361007964072378ULL, 5852485732672557421ULL,  548720187510208315ULL, 8523291497874635663ULL,  561115208940568407ULL, 8210001129546535355ULL, 5617663434425604450ULL, // 1615
 5407693593275839497ULL,  236735178681766491ULL, 6075061142385965514ULL, 5331607435991943944ULL, 7929206654730585737ULL, 3018648260684259594ULL, 3842351904564695182ULL, 7064062059249009690ULL, // 1623
 4622548261891217792ULL,  352597797177838571ULL, 4619966359101644782ULL,  216316986553416546ULL,  895894710286679670ULL, 8745703200996107269ULL, 7995947840294940122ULL, 4828489264058813662ULL, // 1631
 5238145839117585099ULL, 4696585054065825232ULL, 5403480166098488305ULL, 2675737241653295110ULL, 2381439356981642609ULL, 4104706774586579245ULL, 7252578804084731924ULL, 7438078819720555815ULL, // 1639
 4476447825191635739ULL, 3903416991125140609ULL, 8691994599438957625ULL, 3792927963265042055ULL, 4897166173172542108ULL,  247041073701817058ULL, 8455253721678342131ULL, 7850011371181226585ULL, // 1647
  917382741498951417ULL, 6559862470737409875ULL, 4128044843742753025ULL, 1206805654716962148ULL, 5706613173578516585ULL, 3509903423268473970ULL, 7256909221989387224ULL, 6387574976372097553ULL, // 1655
  291914784030388907ULL, 2383027155617268221ULL, 5187353908321019509ULL,  125054621632915861ULL,  267842205138940689ULL, 4530890019104008583ULL, 5447626035242847287ULL, 3969751416051142083ULL, // 1663
 6480753737527768074ULL, 3462499649631946267ULL, 1318469525469705328ULL, 7894910749435108222ULL,  757445696797674001ULL, 1537530605149402455ULL, 3906052344130544009ULL, 1300967894406016221ULL, // 1671
 8992725512163962363ULL, 3958504481217954586ULL,  636578132050818910ULL, 5817855423974024578ULL, 4455654800333087014ULL,  404144229299750260ULL, 4282902755358749418ULL, 7044917581905408141ULL, // 1679
 5680137495284668493ULL, 2925711004742454273ULL, 5953350501178970664ULL, 4800317680800336279ULL, 3778691857466560368ULL, 5501779088498864674ULL, 5039581830616462934ULL, 2659339292903261486ULL, // 1687
 1263369996073389529ULL,  542270648406112450ULL, 1478030842264794359ULL, 2804368471756418983ULL, 7485499476455910733ULL, 6613594443466523514ULL, 7582408348554545234ULL, 4085314653139109677ULL, // 1695
 5719185187494701744ULL, 1814408788736552285ULL, 8608275375204350637ULL, 9159959851943024913ULL, 3729202718631851490ULL, 1624967360558463767ULL, 3017741849637218867ULL, 4354347818319188106ULL, // 1703
 1678778390728165518ULL, 6181059973834816837ULL, 2033372506545629072ULL, 9090494871295873955ULL, 2970569111940112904ULL, 2840530141106648342ULL, 1692485233864968997ULL, 5368779228476836602ULL, // 1711
 4713498417420029809ULL,  637462036323791534ULL, 4574542445600534348ULL, 7261996951585739836ULL, 6012416757146638068ULL, 7849157683068375400ULL, 3947898922308702104ULL, 4087898411344722228ULL, // 1719
 7876751931258088255ULL, 8783486541734860204ULL,  807642759208706918ULL,  982252351390672813ULL, 5907954625818738796ULL, 5107817290493734856ULL, 1525255252035787014ULL, 5788738244188602728ULL, // 1727
 8436412495034217243ULL, 1113783384075678358ULL, 7000250129776951254ULL, 2867956037600036758ULL, 8039372604508395045ULL, 3596081413555443698ULL, 4473875144051456753ULL, 8390576805146672612ULL, // 1735
 8729566179667380128ULL, 3814007443698678015ULL, 7377928657937874143ULL, 4092048771022647412ULL, 8619042287586671984ULL, 2439579065435801821ULL, 1229718506777402111ULL, 7159679167928532718ULL, // 1743
 5431145551134539356ULL, 4230341868736819330ULL, 7425870852958337110ULL, 6997318491978044669ULL, 8592039585855525143ULL, 9005770917016728633ULL, 9054007700021329429ULL, 6969797737949426232ULL, // 1751
 6900294960628090285ULL, 8874038738412794043ULL, 6356692937735195620ULL, 9117362826465542103ULL, 3719209497242272108ULL, 6673288691234774988ULL, 1338515129963680506ULL, 5391686964681550470ULL, // 1759
 3659686339605450815ULL,  754312290447642505ULL, 7496954705047933728ULL, 8104056582763419409ULL, 9121658653251883381ULL, 1484792916688564287ULL, 6836059109231738215ULL, 8289124115955144000ULL, // 1767
  791651758281575855ULL,  344461580008949152ULL, 2459134253239052075ULL, 3677335843334120168ULL, 2572022228961250860ULL, 1903899715498738946ULL, 5736848322170134895ULL, 1456826003168375421ULL, // 1775
 7694243481038850704ULL, 2035347782777305667ULL,  739397041334412940ULL, 3610076366425915880ULL, 8802487787316354206ULL,  366605937295181708ULL, 4326087896602727583ULL, 1704784860138560793ULL, // 1783
 7372148833908712135ULL, 3042712307603848162ULL, 2287698809767225393ULL, 6786254805069279881ULL, 7847300650799571327ULL, 8770258399800891268ULL, 6762369168188499732ULL, 4533939561035740316ULL, // 1791
 3214850664025476104ULL, 1977694722602323798ULL, 7485319672498995252ULL, 4591931360943925910ULL, 1459268337435427686ULL, 4256238245799114456ULL, 4390895314634657518ULL, 1679723849920199252ULL, // 1799
 8010269546085185195ULL, 3147583164129065896ULL, 2219112278049690881ULL, 5934317357726111033ULL,  177248422499263934ULL, 5203817828109416814ULL, 6484916084639233728ULL, 2949486164058078839ULL, // 1807
 7083672691808460009ULL, 4430642415022339421ULL, 1291579943128833804ULL, 3186683713558477296ULL, 4757739037350597142ULL, 8536204518897384056ULL, 4180573028440491193ULL, 2464934426819072699ULL, // 1815
 5714992491634338563ULL, 4042066854521051712ULL, 6322983525439192213ULL, 8777145663825999492ULL, 6234215893917129784ULL, 4216477499623960358ULL, 5271976803076054524ULL, 3972154655659005376ULL, // 1823
 2869772517782633323ULL, 8477897785482418179ULL, 8201998814087801618ULL, 6912200739328244969ULL,  660759382541451963ULL, 3661628129714101805ULL, 7217589553333660719ULL, 7808802946505360089ULL, // 1831
 2515708108479053644ULL, 2419942743089960759ULL, 3380509939564022932ULL, 6115551547149409845ULL, 6731307818699373998ULL, 3887113744770415556ULL, 8274620677895600888ULL, 5912190038655424144ULL, // 1839
 7038693436403473570ULL, 6082373617587441882ULL, 7607925247321702535ULL,  530313993512830173ULL,  772863504576988454ULL, 3886645006137805496ULL, 1095132638610363379ULL, 2476291024874129543ULL, // 1847
 5099573684254993067ULL, 3226160348447854368ULL, 6869950131582823802ULL, 8871437422592876555ULL, 1226996875103533744ULL, 7157798496200591058ULL, 2171075496230645076ULL, 2199266674967817228ULL, // 1855
 9013332289579273207ULL, 6003717111563325867ULL, 2829470571466427051ULL, 6443198097349545921ULL, 1502601185005861266ULL, 2369415092804321574ULL, 3578546982420965387ULL, 6208574570705641668ULL, // 1863
  518567848787765612ULL, 7934832255787682294ULL,  329702745336175930ULL, 2543031861238202894ULL, 1894704735179523537ULL, 1834945132289101204ULL, 4324074827175192131ULL, 4052177125042027803ULL, // 1871
 3092480056514950791ULL, 2288548543091113657ULL, 7366553300531766606ULL,  300912669317501187ULL,  614845670218459380ULL, 2243516270151593062ULL, 7516033886242724823ULL, 3648141284608091061ULL, // 1879
 8663453725303438608ULL, 6199747682841271337ULL,  719127103917037485ULL, 1326484049929581109ULL, 9220237871105943319ULL, 6679612068359245987ULL, 7195640989475600746ULL, 8434975737031081877ULL, // 1887
 2340939356297075845ULL, 6986699639264637220ULL, 1008526849000787145ULL,  129903068656918708ULL,  734568038144152657ULL, 5816765174006154940ULL, 1602138147105937990ULL, 7061831618267624811ULL, // 1895
 2601135918858016797ULL,  812004267191955872ULL, 3557614775773786059ULL, 5934094861871615304ULL, 5299917497192735647ULL, 7875421269303829565ULL, 4898752052070067113ULL, 4336935463244303611ULL, // 1903
 8587177214895039009ULL, 7723812032636176898ULL,  164503339529011270ULL, 1995704546260296871ULL, 1003762407541798865ULL, 9149673297765074111ULL, 8054004137730954709ULL, 3648120388054853997ULL, // 1911
 1802968113019718590ULL, 4752031042509249980ULL, 6598612970220863204ULL, 8915063496670974572ULL, 4853088758754691311ULL, 5947344882519867277ULL, 5430765659597904508ULL, 7768160186632092871ULL, // 1919
 3161171376711043751ULL, 5166902871121669000ULL, 4898943246851813759ULL, 4224746093913218949ULL, 5751705102941125523ULL, 8508606209041349480ULL, 1915808199294148207ULL, 6014105223551500122ULL, // 1927
 7393479217635721188ULL, 9079359198959887799ULL, 3005518094584580122ULL, 7443878590150566219ULL, 7114791348893855436ULL, 8387075625161770402ULL, 5228759746872536416ULL, 8116755817865086439ULL, // 1935
 3977091918350321970ULL, 2492233798673892085ULL, 1999522030511686047ULL, 5555368787035939842ULL, 1644655210555852478ULL, 3110192300415340187ULL, 7773957521611424833ULL, 7279239724311351131ULL, // 1943
 1443689714170555148ULL, 1489412822981853933ULL, 6682905510485257525ULL, 3084442618797179952ULL, 3877770807798334737ULL, 7896509796308804938ULL, 9180009984190745659ULL, 8273089637104708217ULL, // 1951
 1626808186153868449ULL, 3586392998328619039ULL, 8258931291510935528ULL, 2154185313263590259ULL, 4758992703437329292ULL, 4240677875062012884ULL, 5165303098643511301ULL,   30270858026540018ULL, // 1959
  208400407785308225ULL, 1834828580419458616ULL, 1229603052991071000ULL, 2242258703940127095ULL, 7167417410615780411ULL, 4990532380752984730ULL, 7705290038565788147ULL, 1834413186783266276ULL, // 1967
 5582201379926741633ULL, 3735056406677918933ULL, 5339195931474184741ULL, 5297975097647429904ULL, 1930247298913147479ULL, 4184394790545683839ULL, 2611826496225771539ULL, 4481171175663433070ULL, // 1975
 5734349325285650513ULL,  488160787574353354ULL, 2011898922739721743ULL, 2847954200063867794ULL, 3645815954908636675ULL, 7079999652304992962ULL, 2655364524964993856ULL, 2236460142337046155ULL, // 1983
 5111846991640336042ULL, 3631954500472377387ULL, 2637386238544149417ULL, 2102487488611450496ULL,   21838501414665759ULL, 2439811900306663517ULL, 1278175886579615089ULL, 5453891908093968006ULL, // 1991
 4013610801640663409ULL, 4753105548992244011ULL, 8672472187182801809ULL, 5981454018733627852ULL, 6216174290870704873ULL, 5222650057561344396ULL, 3529122440712295732ULL, 7885732679577691115ULL, // 1999
 4207254709911096184ULL,  645268286052568237ULL, 2000872710902775121ULL, 2188902449057766689ULL, 9034638049526185773ULL, 4656376209957878178ULL, 2326325390627234633ULL, 8101967106821323360ULL, // 2007
 6828948776865391736ULL, 3142073877646023740ULL, 2009388326865160264ULL,  149592991280337310ULL, 3738237495856204438ULL, 7873729392421820763ULL, 3607981205442845506ULL, 6684957332066356137ULL, // 2015
 8830405182634996060ULL, 5436504826954411483ULL,  854609351633200004ULL, 3630617064705468957ULL, 3030749592816799867ULL, 1755317259260667728ULL, 9173889358007901159ULL, 2473639141004640383ULL, // 2023
 4265612943891039548ULL, 3834142986209675369ULL, 5515868878175539907ULL, 5277191849489805495ULL,  132606983034467634ULL, 7298094269450501412ULL, 1240267207641778009ULL, 2332452071271446318ULL, // 2031
 2866533145926230307ULL, 2455206205810026339ULL, 6170992141678227461ULL, 4387017861864040282ULL, 5149444512619033920ULL, 5335444676789318725ULL, 6776247450351923291ULL, 2656055897083384199ULL, // 2039
 4201424799589847424ULL, 8093489630291870493ULL, 1250562823928296439ULL,  524655973792612765ULL, 8074858652278717926ULL, 5123757999735044509ULL, 3359057773197903758ULL,  939054172192751093ULL, // 2047
 6001794932377572820ULL,  723361381976272217ULL,  256711613810980568ULL, 2927784730546308698ULL, 2029342328110244702ULL, 1282745925494881600ULL, 6848941188274810724ULL, 1400706101143062865ULL, // 2055
 1205628673311516855ULL, 2320915587625526567ULL, 4418133137507057730ULL, 3839361306350061016ULL, 1444949772101444997ULL, 3361373575996719976ULL, 7195957340236820545ULL, 1806226425421223365ULL, // 2063
 7694688126192248501ULL, 6923795275108125679ULL, 7639967051237808082ULL, 4134183829578467750ULL, 8891437380430253289ULL,   28155084100669161ULL,  132359540796839341ULL, 8344000482860170545ULL, // 2071
 1699684877676405929ULL, 3794179715643136787ULL, 4287115599344027933ULL,  164065737702138645ULL, 7373288293371011168ULL, 1312700873447594934ULL, 7825867061888329691ULL,   96881797805381303ULL, // 2079
 5648515108413797530ULL, 5025210856521739294ULL, 7648885046008132848ULL, 4511047467437590428ULL, 5352952406466264235ULL, 4610584880284155431ULL, 5968063736781991616ULL, 6823300165666427069ULL, // 2087
 5172757362067955122ULL, 4562194594934569046ULL, 9027648862153018555ULL, 5968566291707712882ULL, 8251699648483049960ULL, 3300066680715017661ULL, 1176822427169350308ULL, 3928005790035114068ULL, // 2095
 1194253514579130139ULL, 1667075623672685482ULL, 8889239297949768247ULL, 6936716906873646565ULL, 1493953603646276044ULL, 1280759580117068092ULL, 6055143078740060006ULL, 5906393915884405750ULL, // 2103
  274795546941056458ULL, 2241029324215479271ULL, 5971476810895873975ULL, 7256637493056036769ULL, 6267490744223724163ULL, 2630627059185976163ULL, 4730280611141710291ULL, 5046278672268930150ULL, // 2111
 6288477458923167786ULL, 5544300647305843962ULL, 3668105348049632087ULL, 1749792350724641092ULL, 5581575271922708204ULL, 3400704253121916335ULL, 1911239633327977594ULL, 4417874717761231722ULL, // 2119
 1328942614705679858ULL, 2265107556803300553ULL, 5645127623192610988ULL, 3076851809123442506ULL, 1631705145625872842ULL,  910187465099858006ULL, 3042739676380765797ULL, 3063147843486164108ULL, // 2127
 3446448400750595277ULL, 6062189822762285296ULL, 2641721977704397925ULL, 3053240665788843335ULL, 1619162067473859765ULL, 1413271522285355428ULL, 6537671053209789596ULL, 5716436885365838707ULL, // 2135
 3266678249463489633ULL, 5943661056662247481ULL, 8279917450878733480ULL, 2377680164215400508ULL, 5504619692945365552ULL, 7050236312122446351ULL,   20961729829270863ULL, 8655204467775289124ULL, // 2143
  274088579133517857ULL, 1358591842525317696ULL, 4082632390314949194ULL, 1915735765315278809ULL, 1642405386075177597ULL,    8824119588386863ULL, 9160153529794705036ULL, 6823318070345660841ULL, // 2151
 4483433403826138079ULL, 2891893573909776378ULL, 3340747914789079397ULL, 4228229373204958969ULL, 8557441365292951753ULL, 8169354942353284139ULL, 2945105771521431460ULL, 2822441190994796596ULL, // 2159
 3871837590101820260ULL, 6135004903197897805ULL, 8592865539686791675ULL, 4432892397055835310ULL, 2156375914964067747ULL, 9191975332487127954ULL,  943605484743671935ULL, 5296617146012448541ULL, // 2167
 1112156421423853341ULL, 8967017706419905766ULL, 4234712419045142350ULL, 4074899907092601880ULL, 6026968689095234793ULL, 2923812814340699695ULL, 1398698144715164562ULL, 2967896770121872467ULL, // 2175
  703915004148318423ULL, 4001633674084011173ULL, 7930270300683203782ULL, 1085307393740044107ULL, 3652870553076776496ULL, 2956431586696492698ULL, 7845832059645376537ULL,  800142887387998991ULL, // 2183
 7218187415776390351ULL, 4187520773984935865ULL, 4515663599723217877ULL, 5798309551892526133ULL, 2059931454666388500ULL, 1067962675725567308ULL, 5245004330418979016ULL, 8729165334198537885ULL, // 2191
 3915389082312434240ULL, 6022327839400148082ULL, 2718581010007811222ULL, 3485561524933357936ULL, 8161545926807555739ULL, 1744555561902776695ULL, 5471669811778983362ULL, 6518622387370159594ULL, // 2199
 3088487004096420987ULL, 5696012992962322095ULL,  521819770870565236ULL, 8923410855783315727ULL, 1769700833083555146ULL, 6040380824918506799ULL, 4803860938354063355ULL, 3740252463362539442ULL, // 2207
 9053601097985009423ULL, 2118165329952584001ULL, 7646843501195587554ULL, 8920261636370116205ULL, 2822347929661016764ULL, 4145651299596780849ULL, 3986143608561409130ULL, 2537130899580789520ULL, // 2215
 2923672772465000639ULL, 5455409181770176822ULL, 1280722363688408228ULL, 6027243768872519612ULL, 5923449493205340321ULL,  841756325567205377ULL, 8390426679198519480ULL,  999816380663833303ULL, // 2223
 5121217054837656536ULL, 1546093776759505773ULL, 8721708565502359243ULL,  906333869177092664ULL, 2684428533397995966ULL, 1391330167188791814ULL, 6492886814591070854ULL, 4521830724204910350ULL, // 2231
 2938232916015466197ULL, 3638680093536861561ULL, 5909315871966511754ULL, 7269378478623321448ULL, 3286804384638339617ULL, 4113331725169187784ULL, 3469771558412979485ULL, 1451142732603544225ULL, // 2239
 8231129816449438393ULL, 2912305097721812144ULL, 4240219881342928873ULL,  826778770845813515ULL, 8870624135672778323ULL, 4371848521993037776ULL, 6146570000509219367ULL, 6333326470052819998ULL, // 2247
  424175080610967330ULL, 4080386161521267831ULL, 1191186352289511118ULL, 8942884280894555353ULL, 1014155368478080841ULL, 6931849759614966729ULL, 8945992081484439361ULL, 3851543509729371483ULL, // 2255
 2156856960431817848ULL, 6459844171468831614ULL, 1359115537495312629ULL, 4098353219660895753ULL,  281359839199507355ULL, 7146506556164839457ULL, 8140508953144589495ULL, 6289360715083669184ULL, // 2263
 5005095509655338455ULL, 5674802949478260102ULL, 3272767438745007382ULL, 1450900559870440853ULL,    3787128019714817ULL, 8770849740556599493ULL, 7542370774849142728ULL, 7680157031580996669ULL, // 2271
  939497777585152045ULL, 6872932540200931490ULL, 2979880067359954501ULL, 3304980955688747114ULL,  994743429953692804ULL,  465797705118445476ULL, 5484576460066727114ULL, 8476564377851579668ULL, // 2279
 7901533257804792219ULL, 7462581796959622983ULL, 1098938444990844154ULL, 6237851466918112017ULL, 8072860641608179258ULL,  829132743512453694ULL, 9184350379756163575ULL, 6867715082323698243ULL, // 2287
 4202546902286243382ULL, 3199089439861971782ULL, 6265189312971872656ULL, 1220294837203400285ULL, 7732185866254562363ULL, 7171813087021588303ULL, 8441250960376476773ULL, 5259690220186319784ULL, // 2295
 2129628679491196670ULL, 9070340836726549681ULL, 3189010302413938636ULL, 4331292695345116148ULL, 2646777402702529433ULL, 8430358286769888265ULL, 4446343179243728045ULL, 3508231870385424309ULL, // 2303
 1368604885348856113ULL, 6607945016468877152ULL, 3988019664648371884ULL, 5670354900096551125ULL,  290960356991863742ULL, 6490223781367188461ULL,  820429339279496327ULL, 6628251457545090595ULL, // 2311
 6025441944989899397ULL, 6178625141105250175ULL, 3336668493794425495ULL, 2029579113421437015ULL, 6446971242748127654ULL, 8591201642100872128ULL, 7311266697722843820ULL, 1095460431959759159ULL, // 2319
  360010744729173617ULL, 7090293740242685598ULL, 6308273267393621588ULL, 6844863899130736644ULL, 7156072551600340887ULL, 6108072907046533685ULL, 6638257606194398087ULL, 1703187870648270757ULL, // 2327
  764800550446420781ULL, 3431407720583616605ULL, 9168358815644078743ULL,  861542906030509044ULL, 6697552197341603093ULL, 8061900404527026833ULL, 3105433989055609642ULL, 4241946406574078879ULL, // 2335
 7637394250208130144ULL, 7813475141014845112ULL, 5646144715593933233ULL, 2098157066130201799ULL,  323310610079179438ULL, 2331975086512043368ULL, 2495810264058808149ULL, 1178523689453356098ULL, // 2343
 2693603936354026545ULL, 7362079858746075206ULL,  847546205039766869ULL, 9030548734533276422ULL, 8452995273905705966ULL, 3107173230178716204ULL, 7803065901837537631ULL, 5800501957743839411ULL, // 2351
  234615712007491594ULL, 1716011556935608436ULL,  602200024044971560ULL,  236233625381114628ULL, 2797026559387769911ULL, 7887078846102761228ULL, 6603371671200955769ULL, 8553447637951806990ULL, // 2359
 4452161906590830575ULL, 2712194281548568691ULL, 5692406185617431182ULL, 3621434481452158894ULL, 1165076044577820944ULL, 7257086648774901141ULL, 4854355309381410727ULL, 5961858024751474735ULL, // 2367
 8224821627272906164ULL, 1746359418578002284ULL, 2268666167898117598ULL,  529160248587252915ULL, 4550801753704791261ULL, 1135157516025173410ULL, 8258469593391355662ULL, 2004404956603694081ULL, // 2375
 7157388576965310981ULL, 8786967574758007873ULL, 7235970217379332077ULL, 8548452150543811344ULL,  690265691984006603ULL, 8145816171517735789ULL, 1193011288830674671ULL, 1410219990194511139ULL, // 2383
 3338799699951774783ULL, 9021482526271715456ULL, 5139172448436663040ULL, 1449786564723455026ULL, 8743509832694206706ULL, 2397403553337649717ULL, 3050177202165800325ULL, 2042494813355937534ULL, // 2391
 9118407752388573867ULL, 4610616470151785501ULL, 4791120372762044208ULL, 6308680160162990998ULL, 1294491303007530964ULL, 1802635033551659629ULL,  892054413090642591ULL, 2681963466792043366ULL, // 2399
 6369434430371200543ULL,  614947946185017595ULL, 2807344694213175577ULL, 2751837005092282622ULL, 4649678595952068354ULL,  882717842428617229ULL,  327677035811467625ULL, 8684049536099236881ULL, // 2407
 4531303009191208011ULL, 7353718682110912173ULL, 8006990548942100316ULL, 5580437414139494518ULL,  446779061242818886ULL, 2565612402638093811ULL, 1372555434582549107ULL, 5569687589523362499ULL, // 2415
 7727649827786603840ULL,  803852667904577971ULL, 8249370048764336363ULL, 3639104973050126438ULL, 8704930233574276580ULL, 2152160366977238132ULL, 7447035466968331134ULL,   31947981728750434ULL, // 2423
 5684131837765429428ULL, 2854017790845690693ULL, 2601321436698981458ULL, 4545860164947609409ULL, 6594155615821563551ULL, 4386933972275261821ULL, 3135676402308548238ULL, 6485328874208119206ULL, // 2431
 6917885060652228606ULL, 2951576676237896233ULL, 1621499178254781962ULL,  396187639273674967ULL, 1889132423617023234ULL,  912292607505251131ULL, 4161185868177645009ULL, 2867762295182825546ULL, // 2439
 8329907261663598764ULL, 5089696018941052565ULL, 4932863252011441996ULL, 4755957157302121110ULL, 7523656714619589387ULL, 1046985840232599294ULL,  652768617666455635ULL, 3075915271166254440ULL, // 2447
 5598124219698639869ULL, 4291164709730730299ULL, 3394801555542430240ULL, 8322680777222671861ULL, 7235700350960351069ULL, 5396729835037515683ULL,  955841941402116046ULL, 2795459853519002547ULL, // 2455
 4762900183689048957ULL, 1770233825571259769ULL, 8297340019493941279ULL, 2776038231971428533ULL, 6445710077743471651ULL, 8033585777332116676ULL, 2131966751937454168ULL, 5445760336873835720ULL, // 2463
 7913620956900262334ULL, 5726342332734740061ULL, 5200905358754195477ULL, 7368984456894853889ULL, 4837252423123266947ULL, 5386747863732925601ULL, 2583462352738126481ULL, 5855471530736321997ULL, // 2471
 6843991557152174750ULL, 7818753930977923288ULL, 4928524300178703190ULL, 3292212198047835624ULL, 5194444198298603841ULL,   25969006065001457ULL, 3988554954463739096ULL, 5833129882869892590ULL, // 2479
 5985282350541143741ULL, 4763854352244626037ULL, 7161751253999976606ULL, 5176049351742785093ULL, 6451809029509781530ULL, 8568726006941334387ULL,  298260856870603580ULL, 7158261877525340346ULL, // 2487
 3603158815980719239ULL, 3836839916959342743ULL, 7125063897743063840ULL, 1459173422519529303ULL,    8106016677579051ULL, 1199174970420690426ULL, 6956871771523367938ULL, 6675464847798027418ULL, // 2495
  145033001628114996ULL, 5681597759797782929ULL, 5125413937620065413ULL,  859043861189267188ULL, 2973700249011759806ULL, 2165750277815686987ULL, 5405223325656255400ULL, 1190841485197849556ULL, // 2503
 5854283894429706648ULL, 8316693218794137612ULL, 2933361478162111211ULL, 6852111814504886554ULL, 2037637035190905516ULL, 6938128470275975706ULL, 5860219603508867838ULL, 3489918855069233517ULL, // 2511
 6606168442259621316ULL, 4088664826057782277ULL, 1582419652698032854ULL, 4862061279742433001ULL, 5152106516375391584ULL, 7828081009739639694ULL, 7128451678191855162ULL, 1118967907811586359ULL, // 2519
 4823231858092422093ULL, 7515339291084780683ULL,  764783696357322920ULL, 1474688798534415055ULL, 3971993814658208955ULL, 2573557499260242435ULL, 3579666508879874974ULL, 6614093986449283819ULL, // 2527
 6011620932341716591ULL, 3470673257309631405ULL, 6427095462899339753ULL, 2926788447747282649ULL, 6137174057755408587ULL, 3689787743301859410ULL, 1327047885157310921ULL, 7801617234859273943ULL, // 2535
 5021044743011877582ULL, 4683501046944457807ULL, 2014291516674427145ULL, 8588249170917428938ULL, 5347635073139520520ULL, 6595126712644937085ULL, 8001910989799855166ULL,  666392455154372873ULL, // 2543
 5465235440039219033ULL, 3160828431324285939ULL, 3246428212661292877ULL, 5024788806356254860ULL, 7619114308293649716ULL, 4202483934801897245ULL, 4299960166064267881ULL, 5873069895550950548ULL, // 2551
 8874313615453223255ULL, 5883461311590570157ULL, 7491388748972021762ULL, 7651518422310543396ULL, 7186773081123602501ULL, 3319581328273902513ULL, 9009121764635117066ULL, 1532099884648185648ULL, // 2559
 8123039500187246961ULL, 7919944033903343269ULL, 1557173164631715312ULL, 2306325911703173334ULL, 3212565324798095377ULL, 8899077625226582561ULL,   66166936014239207ULL, 7610158365231216561ULL, // 2567
 6881974391710873498ULL, 1382341607738077599ULL,  295214046617974741ULL, 8765642891232369575ULL, 4833761091294549861ULL, 4223927129250450589ULL, 6847825966079771666ULL,  647123952187159250ULL, // 2575
 1225583295163815665ULL, 7893589105406006849ULL, 3065056754788032682ULL, 2735671891571152901ULL, 7485352820317024010ULL, 4566775535741199157ULL, 7960152963865716957ULL, 7268628268796466225ULL, // 2583
 7223809499789683524ULL, 1545374383547674643ULL, 8461457865433421716ULL, 5777638635146976052ULL, 3949497418429281042ULL, 8691357741095570537ULL, 6534220741441287071ULL, 7321444779214003368ULL, // 2591
 8682177644665940148ULL, 1319188459545857906ULL, 6968204823724671489ULL, 8801484444332808729ULL, 6466237831059970463ULL, 3558333324515923454ULL, 7098449800894421044ULL, 1598402037790466803ULL, // 2599
 1031187391842414591ULL, 3394538766939760273ULL, 4231421659263409857ULL, 4341120144589223566ULL,  726999094922094999ULL,  531498386344708344ULL, 3924215507405455923ULL, 5797651838261192647ULL, // 2607
 4621232972174203019ULL, 5906883477815817285ULL, 1948328609921801906ULL, 7596251364083534744ULL,  406511787363339180ULL, 4394213160050424525ULL, 3534802203907328965ULL, 3380476813084829528ULL, // 2615
 9136391619179032774ULL, 4835262818318287705ULL, 6723820949551517615ULL, 3101988278130614619ULL, 3762116774882753758ULL, 5488667846129702525ULL, 2263057791031775220ULL, 1845981360650054137ULL, // 2623
 9179787943195686270ULL,   26984485395301132ULL, 4014488684757462173ULL, 1095938920389708929ULL,  331076464368742459ULL, 2702590021376302122ULL, 2259395241426248974ULL, 8431868264025814981ULL, // 2631
 3634710379778429293ULL, 6316856058895721820ULL, 3996769967247095045ULL, 8585979336948783715ULL, 3828958964646883595ULL, 6221846994005733622ULL, 6914222793759829796ULL, 3752935479882377599ULL, // 2639
 6597321156266883374ULL, 8775383218510936275ULL, 2179783777901738799ULL, 5809438276290371094ULL, 6138102184633486499ULL, 6376738908399069035ULL, 5371723097420512707ULL, 1346540212955465607ULL, // 2647
  405622142057175631ULL,  918220728524369997ULL, 7858868572022748059ULL, 2937906821021794616ULL, 5132103179137055632ULL, 8556472253346031013ULL, 8004210128533572894ULL,  470220597140590423ULL, // 2655
 6865955661651311535ULL, 6766597054262733848ULL,  670181882990103936ULL, 2333227644968755785ULL, 2641319552362742895ULL, 5982409456828550101ULL, 5071829652083157221ULL, 7796104085832454499ULL, // 2663
 5768973909075394624ULL,  656471870884795016ULL, 8995152847270169696ULL, 6868925946205706369ULL, 3530760467931858415ULL, 7726837919152108196ULL,   64689824363302219ULL, 7689757809703819610ULL, // 2671
 8219290297236933159ULL, 6753012893007855577ULL, 8585646116515139489ULL, 6474384210995851722ULL, 8572835056637144023ULL,  793264242804102722ULL, 1338999263898865916ULL,  675372429151082480ULL, // 2679
 8080321106138605909ULL, 2289071580362851607ULL, 4926222989794983482ULL, 3532613867104189861ULL, 6136651648115776447ULL, 1545209980482721591ULL, 1009766233134412358ULL, 3908614925933883908ULL, // 2687
 5244578574001092099ULL, 8895156675891090452ULL, 1301124283208799233ULL, 6610446279242111412ULL,  156218441999532926ULL, 5071879974856692885ULL, 6769706815975479196ULL, 8603190876725175735ULL, // 2695
 7079096704043652862ULL, 4255385767106016935ULL, 1603515905652066407ULL, 2015559077855926626ULL,  600707346756953239ULL, 4718136993687113008ULL, 3572364807375446314ULL, 1616158077702902602ULL, // 2703
  841635662705701139ULL, 4200423993888251090ULL, 7434111562476416316ULL, 2793347251053151468ULL, 8991208762616768125ULL, 9085547710374348086ULL, 4389107595210327559ULL, 2940827385847037708ULL, // 2711
  910884933623223740ULL, 5026779915088097854ULL, 5760840752455969280ULL, 1031196360483324490ULL, 1379736010132929593ULL, 7972021681251771764ULL, 5152713234789174960ULL, 4545672157735171216ULL, // 2719
 1652750434544148508ULL, 8137108847704343767ULL, 1110222353191716841ULL, 7453819960346770964ULL,  348939250957787973ULL, 7415602616396213376ULL, 6557990151551282743ULL, 6982879104272352849ULL, // 2727
 8329271120489013568ULL,  759903887595020824ULL,  605253938594923567ULL, 2004915894153386456ULL, 7540433597953815517ULL, 6937090766236229067ULL, 1118373256355313675ULL,  240751660823282256ULL, // 2735
 1782115004032754622ULL, 2634613646770283904ULL,  861572531428085995ULL, 3770396431883213326ULL, 8181057210571073246ULL, 5948558628553989500ULL, 3095684978960609819ULL, 3761178371439827210ULL, // 2743
 6494352682772208733ULL, 7068323896537570971ULL, 6312182509260676996ULL, 9084596572242469109ULL,  603433294534047680ULL, 8099018868395415023ULL, 9057706195182997788ULL, 4492930241788823538ULL, // 2751
 7494259003039031143ULL, 4508786519585448066ULL, 7992605463116353799ULL,  342971282145698946ULL, 1018437928186020127ULL, 3242593923097971964ULL,  776223574111446476ULL, 6315706967593993877ULL, // 2759
 2301482523160322344ULL, 5146810839248528053ULL, 4010526576818003364ULL, 4019537065925940238ULL, 2582978643700335211ULL, 6335766422241412399ULL, 2011582391977984574ULL, 4033761957947082850ULL, // 2767
 8732868515734567572ULL, 8638300894776840696ULL, 7598359394293900149ULL, 5229020541974020994ULL, 6049430050767452281ULL, 3507548188476807118ULL, 6252014727049983620ULL, 4872857840612810862ULL, // 2775
 4760541940050363284ULL, 7943790243629045848ULL, 5804332019790268110ULL, 4161656353513125532ULL, 5635139174461757029ULL, 1581251426516901056ULL, 2879375363927738604ULL, 7929190926749465160ULL, // 2783
 4934189827289222664ULL,  667601745801416477ULL, 7102019920444326587ULL, 2702602463911040530ULL, 5144864720287621917ULL, 1530359520233642361ULL, 6810033767308905540ULL, 1503632621690876237ULL, // 2791
 7199514006000499978ULL, 1894900148370600208ULL, 2964006101165356556ULL, 2944412615571819793ULL, 7330607236488520567ULL, 7022494807359563028ULL,  917305385402961653ULL, 3375482406369013732ULL, // 2799
 3849061442923522973ULL, 9160672390978080378ULL,  716334403091091872ULL, 5655787260870076812ULL, 8850053468274709101ULL, 8034706531714059870ULL, 4365992109390363884ULL, 8783918864938364553ULL, // 2807
  539017945015306577ULL, 6122608067472080335ULL, 7512003480485398341ULL, 2878797287100484559ULL, 4369312681835394227ULL, 6605849243680626463ULL, 6406233752712040512ULL, 1914741243075764389ULL, // 2815
 4801043765365294597ULL, 2759632483146377782ULL, 4491944419528381356ULL, 2155205257127808099ULL, 6378194492560365256ULL, 1331969010674894026ULL, 1281506868537252461ULL, 3862948643632041388ULL, // 2823
 2347962817360155372ULL, 5323548857585738524ULL,  605833318290986588ULL, 6255832945404888301ULL, 8880266200144011214ULL, 1038392028362477239ULL, 4396269765425603344ULL, 7095051074782063597ULL, // 2831
 4805174870784794236ULL, 5491319660245024956ULL, 9046731269385087462ULL, 4192373100111747137ULL, 8613064671507408865ULL, 7722368288039146596ULL, 6416857951692607582ULL, 2491724316742444557ULL, // 2839
 3124129569065758091ULL,  178042995336248699ULL, 6794247284307114004ULL, 8705108883188158199ULL,  848814056117100148ULL, 3290897328890333170ULL, 3473262146134101259ULL, 5219025315478825627ULL, // 2847
 1793887885743802882ULL, 8352184268229811631ULL, 9133497858389391478ULL, 7818800841217307800ULL, 8845527444420907771ULL, 9194389994084426407ULL, 8679741985070607116ULL, 5580462089309243043ULL, // 2855
 1054643407150535134ULL, 6310462400343366783ULL, 2969008990679336582ULL, 5076660102199222741ULL, 6312328121372608806ULL, 9062906866191656576ULL,  306761756757433766ULL, 8840655245423346105ULL, // 2863
 6545533085832264818ULL, 3717896762922834834ULL, 2067280769282905433ULL, 5755477359259161920ULL, 8631122659687045414ULL, 7728449533960293294ULL, 8189237586165940380ULL, 1444620088329690313ULL, // 2871
  620672640647927408ULL, 7869399647919348844ULL, 4323909698495030464ULL, 7407504678123700721ULL, 2866873105351092233ULL, 1975084009369830423ULL, 3082227617568995724ULL, 5274284504609762649ULL, // 2879
  338462657882006841ULL, 6860047569618397927ULL, 2082134802258155797ULL, 4095179604013949670ULL, 9118648206364112911ULL,  354005998286009965ULL, 6685796691829194982ULL, 8105022709989493541ULL, // 2887
  330336544876432511ULL, 1672778922654643276ULL, 1250365995315602899ULL, 6067112026384326437ULL, 7103951075679116975ULL, 7290873960627737485ULL,  411191218985265421ULL, 1367195318644854330ULL, // 2895
 3110595663355513297ULL, 3155397304032184536ULL, 2396023743431260489ULL, 6682615890704094497ULL,  627461978753276499ULL, 1152441629613615619ULL, 8835247975605804740ULL, 5396355964057334415ULL, // 2903
 6785142623802399929ULL, 4596458729146408067ULL, 6926046450635545882ULL, 2929375680782438506ULL,  259022713280372454ULL, 5769432141558256645ULL, 4338664032938124509ULL, 1419867811280393786ULL, // 2911
 6140498311611587425ULL, 3418618125052531092ULL, 2602469986503936721ULL, 1604449926833702402ULL, 7914483867891954243ULL, 1319818596837425246ULL, 2790983854900684077ULL, 7468572292417928267ULL, // 2919
 4561937408604477898ULL, 8388263058818827380ULL, 4281857699090551928ULL, 7071237309697651373ULL, 3091144305154406613ULL, 5211094348931529553ULL, 1530552837749467379ULL, 5655695997531393120ULL, // 2927
 1982855234374758558ULL, 6984201163254159615ULL,  728804064630998185ULL, 7815257188283392148ULL, 2122170607532920583ULL, 6946275704458643443ULL, 6627878307013317601ULL, 5265908902134429211ULL, // 2935
 8033134942583872782ULL, 4231055499000784015ULL, 6525066624697487213ULL, 7632501015043089636ULL, 5696218184097308143ULL, 7822647228942165492ULL, 1027813446182023617ULL, 5674450130058087223ULL, // 2943
 4105913277495414856ULL, 7595993905730444750ULL, 2800558307543073591ULL, 4254633237794589661ULL, 6099582803277619030ULL,  612511338507339379ULL, 7169012863272769552ULL, 5470532754346664162ULL, // 2951
 1085848125737989918ULL, 9070396371674031780ULL, 2557136990483815597ULL, 8003753643432595150ULL, 1876376642274896829ULL, 6256754159573123455ULL, 1634627986136508183ULL, 5914858769013702621ULL, // 2959
 6143111511381389548ULL, 1351886571051043921ULL, 1251987658193656847ULL, 4643026697145681506ULL, 7584056709949123583ULL, 1632287500200144540ULL, 1910586237292530020ULL, 2285101264219240749ULL, // 2967
 7581036475334448367ULL, 1383977074463737613ULL,  388278907751099225ULL, 9168156603544611897ULL, 6767387516561541790ULL, 5168845640630400149ULL, 8909370985481845359ULL, 4919184731622680852ULL, // 2975
 6147813010678698527ULL, 5549408244225630080ULL, 2654219068222131604ULL, 5527999089193888147ULL, 6224600940169556664ULL, 6544601275536113059ULL, 5039734813528516525ULL, 1908249503637830814ULL, // 2983
 1738456097644107426ULL, 4312200676676709944ULL, 3456585261290609031ULL, 4391390557568686354ULL, 1235151939217180715ULL,  179244206840649178ULL, 2197196529838670363ULL, 6750261347852709366ULL, // 2991
 2146128199987311700ULL, 6521438168239981160ULL, 4045360461887583065ULL, 5815251007378439035ULL,  762979779560801322ULL, 9181776542664450605ULL, 2742810744665386991ULL, 9200113840802539635ULL, // 2999
 5158880593991524982ULL, 6608001847704701068ULL, 8545927726138503453ULL,  392694559424733218ULL, 2112884525467955015ULL, 1478858516345158627ULL, 5670367704728712427ULL, 3431718561116702108ULL, // 3007
 2082045384714139472ULL, 3393471133923207975ULL, 3555849919523451903ULL, 7173995209656602810ULL, 3121830348359163841ULL,  898172251023827968ULL, 8999053729208750514ULL, 1122535896331785793ULL, // 3015
 5163856533448581918ULL, 4326656102625374246ULL,  283186075600322668ULL, 5044119853380701572ULL, 5291289428315489861ULL, 6706151658522386709ULL, 5528726201363919681ULL,  331408959755707503ULL, // 3023
 1644282879581187765ULL, 4514805395825005882ULL, 3710230193830819384ULL,  295590457039149789ULL,  374456247238334683ULL, 3473329594064790953ULL, 2068676758739602256ULL, 5084700225937809077ULL, // 3031
 3103031197578287800ULL, 2495573478065717931ULL, 4907334955905998628ULL, 5782287872099404504ULL, 4839299670759954839ULL, 2713537441408655513ULL, 4179565682993779359ULL, 8755425421347157865ULL, // 3039
 6769826494843278494ULL, 1800609320529863689ULL, 6512287344649253527ULL, 8088745196156788944ULL, 3289962481337023940ULL, 7036881535774864895ULL, 6934568245910864484ULL, 3367800491115067267ULL, // 3047
 3086194020861272976ULL, 4200444679812986944ULL, 4179695270214879838ULL, 8968781324133984285ULL, 4024428015267081990ULL,  940276739389157581ULL, 5503893134147194302ULL, 4804470221833569017ULL, // 3055
 4519188899903960281ULL, 4307032246102502706ULL, 8701279317784962537ULL, 8694847801733509858ULL, 5511108165213770876ULL, 8126509000196353217ULL,  183194992951688597ULL, 4036531783051719676ULL, // 3063
 8134311427932397171ULL, 2039545949430490073ULL, 8996336977922322261ULL, 2886257563265076422ULL, 4243901969692529836ULL, 2778014615593230336ULL, 4298864422240806345ULL, 3574770659120645318ULL, // 3071
 4964192342935456252ULL, 1402785492988428818ULL, 1830836278067855355ULL, 7209969383985370002ULL, 7382618560668245461ULL, 1340876778549226327ULL, 8384043803931075736ULL, 1611830528430636176ULL, // 3079
 4391012987610876816ULL, 1162245819446422493ULL, 5436331718865792096ULL, 7961370887160535360ULL, 7875037685365732919ULL,  981284716541010807ULL, 9098498307620756537ULL, 2545211356041754275ULL, // 3087
 3214486244030028343ULL,   58046200712304154ULL, 4822258104749862314ULL, 3163894926377250474ULL, 4157749895169845760ULL, 1323946145328490219ULL,  658808229672646997ULL, 1390032816105099684ULL, // 3095
 6587153155915219941ULL, 9213799148109430730ULL, 6600782020410504742ULL, 3256974487482298707ULL,  244439427459404362ULL, 8202977735378258014ULL, 8794314575389998344ULL, 4958884311926822073ULL, // 3103
 5472813901447935928ULL, 7830751306810618226ULL, 3061574056187057280ULL, 4053204602201321698ULL, 6276045907702020637ULL, 1314373574600789272ULL, 8312927421288938313ULL, 2761303319950899287ULL, // 3111
 5256685026257411135ULL, 8476821376128135028ULL, 1480156390618485035ULL, 7886542674439634626ULL, 6748683028631483794ULL, 1844161518450758137ULL, 8390965431823320611ULL, 9105054356174408154ULL, // 3119
 2596604304014446981ULL, 5712107270054470461ULL,  260335787756051304ULL, 3654130276851115141ULL, 5919090578635860973ULL, 4247863798125447416ULL, 7672910242157793371ULL, 1461982468712113765ULL, // 3127
  537525508132157809ULL, 6340318241373568767ULL, 3225855636888614561ULL, 3742277714681048594ULL, 2646265223656703202ULL, 7070792200126996173ULL, 3166113024507127485ULL, 6454265915041728736ULL, // 3135
 5441536106574619635ULL, 2197523651868302920ULL, 3484940979347472446ULL, 3014881555081450721ULL, 1596785739021579371ULL, 5189305488493548386ULL, 5048540432280985384ULL, 3752547180179992928ULL, // 3143
 7366719767338618784ULL, 7603747837016302390ULL, 5872982265804697121ULL, 2120370002480231028ULL, 7709092752269349203ULL, 1109734071231872521ULL, 6920264683051596265ULL, 7414551066295791698ULL, // 3151
 1283629097660248839ULL, 8840300649249594680ULL, 6240356605733769576ULL, 4949229600283762545ULL,  671183485975875570ULL, 7883466293374913178ULL, 7566451011275680922ULL, 2082417823962711988ULL, // 3159
 3282134817103948890ULL, 7079002113426948732ULL, 2585447147556748338ULL, 8450992537662754174ULL, 9167162275217180210ULL, 2723001600745538965ULL, 7901354560460935793ULL,  779111639478148601ULL, // 3167
 1302883311495873666ULL, 4730181698274130110ULL, 3027850419349237067ULL, 6157010231572667326ULL, 1371202313625651970ULL,  195385795317132376ULL, 7229745920497967698ULL, 5424080031953564630ULL, // 3175
 2740597243404082935ULL, 1220253751095978279ULL, 3255710185430657859ULL, 6397212251784669359ULL,  785228828238774829ULL,  840183312647254417ULL,  811022445861987373ULL, 8648195007818635799ULL, // 3183
 2015335197555919548ULL,  433773646322663066ULL, 4611043935236074244ULL, 8742219530820203844ULL, 2184516326985875632ULL, 5696527536908283298ULL, 1992036902119953834ULL, 1479398909228724655ULL, // 3191
 5176945638385326027ULL,  835306501777575883ULL, 3147526918671110524ULL, 2408784215049237635ULL, 7129360569237677760ULL, 3395967098754820168ULL, 4868262473379444127ULL,  830916739897717660ULL, // 3199
 6975794738956670260ULL, 2703411253133228130ULL, 7855474259820743822ULL, 8345712886199694910ULL, 1936492032086249284ULL, 1007508756285943873ULL, 6716103918260274521ULL, 8661163086172690831ULL, // 3207
 5186560330134338758ULL, 1878961311047000114ULL, 7505616304657736150ULL, 3043470954565591533ULL, 7536713049497762506ULL, 4128615813138043779ULL,   36856086184316053ULL,  841829117955535045ULL, // 3215
 6224222939256142166ULL,  152745427771662850ULL, 5767499120334902991ULL, 5672943714321437475ULL, 4093954663369784353ULL, 2409148054067546881ULL, 9167360140417017172ULL, 4256364062418624158ULL, // 3223
 2120036652333469163ULL, 4241263643499769949ULL, 1199698858412118917ULL, 5813885755029583959ULL, 4500800614530997376ULL, 2694643352782569146ULL, 5678662088643580666ULL, 2326935486854040286ULL, // 3231
 7081712846121834663ULL, 7535838155414540852ULL, 1754767189594801441ULL, 2106459045168338313ULL, 1442490270928775355ULL, 7435408393444901564ULL, 6362546200473863451ULL, 6517026808187596842ULL, // 3239
 8603725792474374186ULL, 8884863772943762120ULL, 8819653010750468818ULL,   93092485086822911ULL, 6194507026726389498ULL, 8634738286994520167ULL, 6324208312902463545ULL, 5329310067412657732ULL, // 3247
 4217982653766971430ULL, 7808389049624000599ULL, 7627186023148592592ULL, 2598099661619066505ULL, 5207083157173448299ULL, 1232782629566125211ULL, 3278536443660393119ULL, 1605468143187543692ULL, // 3255
   61355811436569932ULL, 3238942815459192440ULL, 6742337372542583924ULL, 3754718375906436976ULL, 6119771142710374705ULL, 6363269438781908322ULL, 4904386365187449629ULL, 7403156540927584843ULL, // 3263
 6110983661754663966ULL, 5871746831903869066ULL, 6679649611634372738ULL, 4361101903123589242ULL,   56610474877352024ULL, 5009618059188032115ULL, 4120321931441177050ULL, 5994037117817736640ULL, // 3271
 7882046079504622164ULL, 3839314526062526277ULL, 3341643196968168624ULL, 9114483779754111542ULL, 1536745493307852429ULL, 3458649719434346316ULL, 8723588657463485246ULL, 6340128842742430957ULL, // 3279
 7626607775056481337ULL,  902625891409594699ULL, 2234978094459683978ULL, 7746246081789123497ULL, 1634240288220638938ULL, 5626735487874781145ULL,  924206267495696157ULL,  712867923537303515ULL, // 3287
 2407008460964927953ULL, 4983891733927907386ULL, 2922843314714017237ULL, 5986693960756864100ULL, 1906012623801195017ULL, 1677348625367428620ULL, 1860405866843589960ULL, 7017429524625794212ULL, // 3295
 1782609071194091632ULL, 5346526954881373757ULL, 3960411171566313397ULL, 6309175734990811612ULL, 7401893106085584900ULL, 2125841640446508868ULL, 5109939750553591630ULL, 7908979688021790866ULL, // 3303
 7390892011436158527ULL, 4042227832596840354ULL, 8544502861922165565ULL, 5549952093022302327ULL, 1027521406277814198ULL, 2633372697573456525ULL, 6021406151792298365ULL, 3151568878166699648ULL, // 3311
 8347485605674831138ULL, 2598230351785389800ULL, 3144124793861535396ULL, 8679176200173321063ULL, 2396573231637275258ULL,  425373201966333385ULL, 4420355367748866507ULL, 5800089159002094313ULL, // 3319
 2780480236080787240ULL, 3678238627330681888ULL, 1424494713390571153ULL, 3328754510016761771ULL, 7232119401887939355ULL, 5339943392789789510ULL, 6389557397229660523ULL, 2610796709399527047ULL, // 3327
 7766236062854819459ULL, 8598195699993633636ULL, 4893061113253826100ULL, 3009634682953923536ULL,  412273632369940856ULL, 5572775292374676088ULL, 2545988731611154422ULL, 7420504338154089294ULL, // 3335
 2768437367118669804ULL, 7428080028840118660ULL, 1880189609980720134ULL, 6644948204472593604ULL, 7495589711739806568ULL, 3919090493986829242ULL, 2029659790214353360ULL,  952073994867180384ULL, // 3343
 2515542227716497329ULL, 2259512636075976060ULL, 8380897525613184401ULL, 5474865646859165332ULL, 8704155197507705574ULL, 4402428116952189516ULL, 3973761312606092909ULL, 7353240864250993147ULL, // 3351
 4474931344734014729ULL, 1711758731969162454ULL, 7091411360385924270ULL, 6244057931876102193ULL, 1894854457847103909ULL,  802032070530870506ULL, 7469663592394511917ULL, 4497038064275854282ULL, // 3359
 2081003731994023696ULL, 8170437122079073219ULL, 2802325978231986834ULL,  808328341880781738ULL, 6246199634462528356ULL, 4309881029001517141ULL, 7810316879231957905ULL, 7738787592086091819ULL, // 3367
 7997698712634070479ULL,  193625107118639530ULL, 8583881223642234525ULL, 2005995034581398165ULL, 7377459423707930055ULL, 5179877890548536248ULL, 4562133176952770506ULL, 6385584762503899602ULL, // 3375
 7210094616173961416ULL, 7881666125404259195ULL,  531208545104367597ULL, 3072157694288605396ULL, 4677378893558203676ULL, 7773997085485774116ULL,  598416544980564858ULL, 6326199920899098952ULL, // 3383
 6516586930065052241ULL, 5238481259072562119ULL, 3734136025862737102ULL, 7132459757192106289ULL,  829131364058936796ULL, 7511974394111041161ULL, 3542509531002965100ULL, 2811029410956242049ULL, // 3391
  783464930633586161ULL, 2318280667873323151ULL,  935945934230957858ULL, 8092081651009882416ULL, 3549105055039726221ULL, 8877648559429580011ULL, 3708747309945645988ULL, 3520264820780150608ULL, // 3399
 3276929434636865831ULL, 6879058320008433380ULL, 6779850334504413556ULL, 8899288877510461579ULL, 7877111653379114238ULL, 3776874204867765495ULL, 2638706317672116080ULL, 3725481262144421535ULL, // 3407
 8057227123919667572ULL, 4736844726191139647ULL, 2210828257472381074ULL, 5383125849085011156ULL, 1024889007427318468ULL,  684082875677622566ULL, 1794506778278942708ULL, 5735598516233919582ULL, // 3415
 3739721737308226446ULL, 2859129638708119312ULL, 8179430839733341015ULL, 8905181735668698195ULL,  499565672980788912ULL, 9029419603784982976ULL,  823215489093370562ULL, 6560443245401058177ULL, // 3423
  351918724385081229ULL, 8650243630013920461ULL, 5679470272936184624ULL, 8322680296517053246ULL,  624027779196679010ULL, 2214623556586724445ULL, 3987738829650189531ULL, 7489970770391430257ULL, // 3431
 2118134835353445373ULL, 9023660597621312876ULL, 3660774849461095197ULL, 7907364096637173674ULL, 2940782169704598282ULL, 7298612517389756397ULL, 2021568457934717385ULL, 3421068230661263876ULL, // 3439
 6709599654231009838ULL, 4936234162029777270ULL, 7657937268212047987ULL,  646685135968629588ULL, 3818933552736987417ULL, 1477127563734605611ULL, 1588158734963673197ULL, 6310760908195849821ULL, // 3447
  869454669516033822ULL, 4780487210696612799ULL, 5593147734985297290ULL, 8690570045713980424ULL, 1954518895044132051ULL, 3074555522338121313ULL, 2178122211035256675ULL, 6349574533151164402ULL, // 3455
  120191537817534263ULL, 2830047720871393008ULL, 6097979080018220573ULL, 6836721812288566144ULL, 6338041553690343926ULL, 8500212980435092778ULL, 8057575677589399112ULL, 2409121817821392589ULL, // 3463
 2475279290326228817ULL, 4233887829227786145ULL, 1430716257847272949ULL, 7378984888851678576ULL, 1243524321038725022ULL, 7361322505870254436ULL, 7725792125186925623ULL, 3085996362632956050ULL, // 3471
 6549961664787776191ULL, 6400740434326749976ULL,  169404901342112199ULL, 4118109305999136786ULL, 3104567551076419908ULL, 5210274700389246496ULL, 8982552105650587844ULL, 1642429502061700338ULL, // 3479
 5585633509873868666ULL, 1079514343283823857ULL,  354031132521701436ULL, 1178212888052738104ULL,  465295567468267058ULL, 5019201987781891803ULL, 3803688361382343412ULL, 6813699314509909463ULL, // 3487
 4797870390621970160ULL, 4554846697266564752ULL, 8005157926037391240ULL, 2251349710141762677ULL, 2844534215990379487ULL, 3825124632070078552ULL, 5857648898329323396ULL, 4838173637465781432ULL, // 3495
 2120499426419005917ULL,   12888102214782062ULL, 5152815171735364618ULL, 4072086012501133811ULL,  507264351630704196ULL, 4585826390709081254ULL, 7973114307400646716ULL, 5441230700180907755ULL, // 3503
 6167221382493582190ULL, 8514887955279407076ULL,  222289322708655134ULL, 6835360711935232963ULL, 9004490045539854064ULL, 5670537823485226144ULL, 6904667439134830950ULL, 7858677276215334258ULL, // 3511
 7203027406993320706ULL, 2276325387639768413ULL, 9062666370845120136ULL, 8750581281077541193ULL, 6216327359274184735ULL, 4657511396486612484ULL, 6289189309738512494ULL, 8513682288840413063ULL, // 3519
 1648075418257957483ULL, 8182045929201000146ULL,  124691805419113414ULL, 4937188281813130886ULL, 7231147909284509361ULL, 5544576718971109674ULL, 2669693496834780286ULL, 4714238138116141914ULL, // 3527
 2828075299907008637ULL, 3781819408847234701ULL, 4115602886894553096ULL, 3013928317370917841ULL, 7422064296591781318ULL, 6074627836986534018ULL, 8546809771522791109ULL, 7720920222705353232ULL, // 3535
 3946764265824890741ULL, 2841877893892585401ULL, 3250256682478259064ULL, 3977265881053228529ULL, 9163420242001813861ULL, 6170475864325073472ULL, 4478352517206263224ULL, 3259090571102627172ULL, // 3543
 8651905495637317202ULL,  750425418450816315ULL, 1126566598312569799ULL, 4652694557138540161ULL, 2212421414971972322ULL, 3813140423230126018ULL, 6868888450537436941ULL, 2507372302565960407ULL, // 3551
 8990282728427248310ULL, 5663736746456588734ULL, 3904944331014518991ULL, 4275199928958724184ULL,  716101151677120203ULL, 6454734242438342679ULL, 2883645728457912371ULL, 3277509451289363128ULL, // 3559
 7531362756636055916ULL, 5856315535065031904ULL, 7792288607709397248ULL, 7983188212998201026ULL, 2789588414766578277ULL, 2317197133319097737ULL, 4883645212749221975ULL, 2027385505809307637ULL, // 3567
  950447595488828144ULL, 7667723282667393340ULL, 8108752840773454178ULL, 8700384471254838771ULL, 3941854933347847212ULL, 4795935624479182000ULL, 6422199453524599686ULL, 9137679851193696998ULL, // 3575
 2878007910801432412ULL, 4164747487104762406ULL, 7056261402605265704ULL, 2228262465335163966ULL, 5497520266916706157ULL, 1057582606818823936ULL,  146657001979511335ULL, 5808349347132846802ULL, // 3583
 1552718325891768488ULL, 5952496528266653910ULL, 6972251769864289698ULL,   39581083258761784ULL, 2137883598355379412ULL, 8516235330310604334ULL, 3685589753094164050ULL, 4066901184036115788ULL, // 3591
 4977794452903735515ULL, 8010522145551650315ULL, 1932840299681773659ULL, 3433161601318777233ULL, 5560872176981267473ULL, 8588154011557115789ULL, 7575712322913216391ULL, 6804633782871569232ULL, // 3599
  202459880073358957ULL,  343157743908139579ULL, 8963267232655196912ULL, 8865446312000042461ULL, 5218255541347296092ULL, 1214489811328487454ULL, 7365480708955653408ULL, 6244070915039829853ULL, // 3607
 4289667629650705629ULL, 5930586947953805823ULL, 6046633599916226481ULL, 4429496461223666945ULL, 4631120720555408418ULL, 8091662921150980603ULL, 8967409759908677357ULL, 2888519625006509018ULL, // 3615
 9206682937156254065ULL, 7121209250917425513ULL, 3614416196081549960ULL, 1600984894552667173ULL, 5698221094663787347ULL, 8513144988573079443ULL, 8096865694803306926ULL, 6960232891769278063ULL, // 3623
 1341692855787545688ULL,  162297186519391172ULL, 3807824315286115326ULL,  549088163186681804ULL, 8386072085816548692ULL, 2199034007748080587ULL, 5090303714650660626ULL, 8076607407702743452ULL, // 3631
 8319230999521754554ULL, 4796820713201521893ULL, 3514356106678342221ULL, 2319574859322598951ULL, 9213280307192892750ULL, 3829534933399502355ULL, 7143191677799036075ULL, 2026563218033368456ULL, // 3639
 5233843591182312688ULL, 6649838956730545422ULL, 6780654052295817746ULL, 8257240903307692304ULL, 6616306165252630178ULL, 4850091866830814121ULL, 6320456504808103040ULL, 7556852455853170232ULL, // 3647
  454399818294431819ULL, 8126590626223610492ULL,  304734698804362281ULL, 3957961089460127800ULL, 2832141255437368927ULL, 8381416936431386740ULL,  130519770023891662ULL,   13473399555886094ULL, // 3655
 3373468522162739016ULL, 5182659228672372910ULL, 4638867437201399287ULL, 6874104632418920642ULL, 5449430973621253785ULL, 4515039406500285005ULL, 6204151697926257072ULL, 7962830911197146451ULL, // 3663
 5978820959846079396ULL, 1403935402191203476ULL, 8088842944962447475ULL, 6578198629940404548ULL, 3926020475508701977ULL, 2449573059926669789ULL, 6920851644979511220ULL,  197531572031505830ULL, // 3671
 9126358815768987400ULL, 2001698663596288088ULL,  373346867564326930ULL, 6573655779567380888ULL, 2153255719407908229ULL, 8369293280612678084ULL, 4713842972564085867ULL, 5792586894552594737ULL, // 3679
 4751429614371286759ULL, 7752847554205831132ULL, 3335046753687837331ULL, 5314512686023999021ULL, 1620545639953699545ULL, 2094235444316808083ULL, 1003760168578448885ULL,  388973378365909387ULL, // 3687
 7671957819199676302ULL, 5448601161460787708ULL, 2043103303270114045ULL, 4644710486799840844ULL, 4664208049091315578ULL, 3330394405304895415ULL, 1676011848658016040ULL, 1623970880356015093ULL, // 3695
 7096131561893996207ULL,  820969946506001770ULL, 5261120542851046642ULL, 8468873514366047982ULL, 4676196341625893793ULL, 6199691426588213850ULL, 3631503933881426875ULL, 6586703455549519508ULL, // 3703
 8979336849063804360ULL,  902022366135554795ULL, 5610817480033956901ULL, 5995427136009681223ULL,  113992550933330248ULL, 1206332472776155012ULL,    2058771757482471ULL, 8217445862620649088ULL, // 3711
 2983749748691756875ULL, 8305996616673503704ULL, 5950526406949359489ULL, 5903164431050322953ULL, 8891235009570405192ULL, 7083307219777336505ULL,  244776591030592072ULL, 5379456627118350925ULL, // 3719
 7258571216480127965ULL, 1799809516571279573ULL, 2604839813629492848ULL, 4697670147634838433ULL, 7897686161335728923ULL, 4508836766301653033ULL, 8734305975690647199ULL, 5774563232037397913ULL, // 3727
 3317954364339401364ULL, 1516181940068172328ULL, 3185313869186125880ULL, 1448459446154462520ULL, 1075458163637415061ULL, 6152543748498811523ULL, 3755033269696587070ULL, 1320976157907627758ULL, // 3735
 8590107336311259657ULL, 5436249108981248286ULL, 1692650292352575968ULL, 4690407477648799794ULL, 6814549848762238950ULL, 8266709352074224125ULL, 3478782794868236037ULL, 8820167475125738608ULL, // 3743
  451716322258196232ULL, 6841845897936589744ULL, 8532323758047565001ULL, 6490207029051110080ULL, 7598699975315559130ULL, 1704644633055760444ULL, 5728007083752499732ULL, 3920593663921760564ULL, // 3751
 6146406467589779181ULL, 7066317498442443927ULL, 1044017957957027603ULL, 8206021181070851528ULL, 2509225144184661285ULL, 4960679557462601086ULL, 2843887006692370268ULL, 3561373061405758916ULL, // 3759
 5670452374072699014ULL, 6932633518247404964ULL,  246780231871332957ULL, 5363813975800725166ULL, 7618847259728819624ULL,  752469380636970319ULL,  870707365112581652ULL, 9218224691983010778ULL, // 3767
 4806533782754447575ULL, 5632798560084907471ULL,  371151051657403707ULL, 4485747510575965923ULL, 2641434161589023582ULL, 8868384130599995019ULL, 4780530022622387792ULL, 8780924499379443999ULL, // 3775
 4386232079786034628ULL, 6207014457253282854ULL, 1466282460803487528ULL, 3255120484136967512ULL,  192542972495909311ULL, 3985239986009107596ULL, 8680652909332668715ULL, 8080364172458335446ULL, // 3783
 1817890753558278361ULL,  890994354794072556ULL, 9105238395694483005ULL, 5069417996762779765ULL, 5599796894406346033ULL, 8008621695152575574ULL, 7920815252101428047ULL, 2384565246456719959ULL, // 3791
 4832988105889508408ULL, 7716687606690054452ULL, 1715664063054459219ULL, 6161028246075559984ULL, 5756025912303733044ULL, 2971457375306343142ULL, 4902988838514717988ULL,  253749401011706978ULL, // 3799
 6318240202303402594ULL, 8909921399436162065ULL, 6521485623323301662ULL, 8723407083719324219ULL,  247025419439840134ULL, 4054865367491280848ULL, 5851458867134559238ULL, 2028143923276728297ULL, // 3807
 5807638276508260517ULL, 7760345502862287775ULL, 2269895542789285802ULL,  208137342553279755ULL, 5620897909460447372ULL, 4015856205167352638ULL, 5008044224474558382ULL, 8021394309635836845ULL, // 3815
 5414349368427290094ULL, 8303018953213778607ULL, 3240538996854096965ULL, 5610373435770687835ULL, 6088338707388158843ULL, 2432033044537978530ULL, 6881297376060226387ULL, 4177500469542266816ULL, // 3823
 4981636463074197417ULL, 1765493927011589617ULL, 7412475647632850734ULL, 6054081430544177202ULL, 5153225985277008621ULL, 5110516233506395499ULL, 5116171207183297296ULL, 3040810564967460011ULL, // 3831
 2393110143797387480ULL, 4019611493651627531ULL,  700139442402530373ULL, 9121213556945421545ULL,  848479658974732434ULL,  281531650603855682ULL, 6790051534590814743ULL, 1971968616041377758ULL, // 3839
 7173506055695901281ULL,  576475936261394708ULL, 5711093812617836747ULL, 9172611188859982155ULL, 7477122963514842295ULL, 2578845931789377108ULL, 8968293896094025679ULL, 4677070672599175367ULL, // 3847
 7740113978083299930ULL, 7771681141540638149ULL, 9103295060965826105ULL, 6005359535569227361ULL,  776025189405132346ULL, 8458179715973257905ULL, 1522551273759397030ULL,  891020650098891281ULL, // 3855
 4944238838212827230ULL, 4835294961221982359ULL, 8098053948870890605ULL, 3072908372868474082ULL,  620917461884014745ULL,  498354976814512364ULL, 2048038766707396149ULL, 2503871319864934672ULL, // 3863
 4648735780957198470ULL, 9005034132716717872ULL, 8721703086182080899ULL, 5257061483859064203ULL, 2850540782896960308ULL, 7840432962728384526ULL, 5698645460284889804ULL, 3845777351404363490ULL, // 3871
  975578162332785990ULL, 2851472877766313044ULL, 4242234388998758748ULL, 6202064949879857879ULL, 2352763522732829804ULL, 5228991172006038109ULL, 2652473543548249463ULL, 4965582997376146226ULL, // 3879
 8785042918569253442ULL, 2606496090571437245ULL, 1310894689961965555ULL, 8557730206628995971ULL, 3132054698405788293ULL, 8534527531662766850ULL, 6682872708475104690ULL, 1026840387773810813ULL, // 3887
 2614633119836440925ULL, 7508710940861824171ULL,  579322477172651528ULL, 2496647318568230062ULL, 1964451745873984326ULL, 7332888289345707286ULL, 6235128947737948793ULL, 2694762572777938619ULL, // 3895
 7822344343105165994ULL, 4856801762641692802ULL, 3941444196630134209ULL, 4071302464776314309ULL, 2142579028063741847ULL, 6680827021166792088ULL, 6539390801501692587ULL, 7260530568344477761ULL, // 3903
 2362608631183500007ULL, 6787519389023590082ULL,  809901291531140207ULL, 5874017108261632867ULL, 7786433163458796156ULL, 7391278326827358323ULL, 7058632610619642050ULL, 1371617869087103410ULL, // 3911
 6163927526099896999ULL, 5567471908787420682ULL, 1196207525142449721ULL, 7955498580911177903ULL, 3797860296293264534ULL, 2940866255037745946ULL, 3897248930866570333ULL, 1044530945423539018ULL, // 3919
 6523894263173941320ULL, 9201788676848672819ULL, 7892845007331657084ULL,  884776553107946605ULL,  612595074300802064ULL, 2030724173570354415ULL, 9138723742685826063ULL, 4105460562788216896ULL, // 3927
  407389635383994581ULL, 6961278913511235359ULL,  864962769282337306ULL, 4942383718027603167ULL, 1882986988083539478ULL, 5776702126515783154ULL, 8861274766035247958ULL, 2816721450587855287ULL, // 3935
 5429911365236708168ULL, 4272220505909751894ULL, 8647571834542314880ULL, 1331918437089458365ULL, 4209679902098227619ULL, 7708022552613817956ULL, 6764984653317270605ULL,  980938800857965674ULL, // 3943
 3039671511120637166ULL, 8775971449227709489ULL, 4412251137229546328ULL, 8567457345978576313ULL, 3154861073053561098ULL, 2852102011703387105ULL, 2718648466429162727ULL, 8954560790293479423ULL, // 3951
 8463961548578027394ULL, 3024572136967135475ULL, 9160406314071186712ULL, 7924956218253907603ULL, 7719133182568922973ULL, 8271745785096432750ULL, 8999717812560208795ULL, 3209748048730423501ULL, // 3959
 7971530263468823650ULL, 6720651567229044626ULL, 7257330597946344975ULL,  232275452301904168ULL, 1962152275137652982ULL, 3981583432084196218ULL, 8753200924149050017ULL, 3605988542820361740ULL, // 3967
 7716181440576388046ULL, 6658579747430575909ULL, 1763679212694347953ULL, 2576557860252661665ULL, 2546398621692914352ULL, 5520186157439912889ULL, 1654244159741424872ULL, 5138761686371901142ULL, // 3975
 2268909632566401413ULL, 3562811745904099588ULL, 8700778095246498740ULL, 1491687823508133550ULL, 6879464666506262325ULL, 6120359081538642568ULL, 9186043436820262305ULL, 5179711954965545977ULL, // 3983
 7133536260849274772ULL, 6108696523627381333ULL, 7975083590076086488ULL, 9156655827657150548ULL, 1086813953372102150ULL, 3620854574460056020ULL, 4960032121852815508ULL, 3143460495174032441ULL, // 3991
 2172285445018318611ULL, 7531809948077187502ULL, 1277987411019294570ULL, 3089249839086901105ULL, 5273396994617842308ULL, 5343373594471317622ULL,  489212464832545422ULL, 3691549200417911188ULL, // 3999
 3914633175975950223ULL, 7296592160223183464ULL,   38756029920816608ULL, 3964454908406453231ULL, 3459973866708037321ULL, 3866628096406445781ULL, 7121553711138657902ULL, 6425575703977810296ULL, // 4007
 4492988795803834445ULL, 1720158618417274952ULL, 4534139349930767235ULL, 4705056245346426455ULL, 4795645339127460275ULL, 5820232702277162541ULL, 2124771315545056062ULL, 3684234497082017380ULL, // 4015
  865283546588363691ULL, 8705749227160718132ULL, 8987330577918434184ULL, 2029609555507131761ULL, 1808769544724128999ULL, 2420566359477772719ULL, 3682954206639279958ULL, 9000790370870020311ULL, // 4023
 4356783639653545550ULL, 4723547172411467610ULL, 6306985412084179162ULL,  251715260423370712ULL, 1030289181718602880ULL, 7164116522611836623ULL, 6360357824245863879ULL, 9194464997374599819ULL, // 4031
 3382433609731954175ULL, 8129680945195924221ULL, 2900302247390678242ULL, 6370324554272340952ULL, 6832156117909341365ULL, 4416023011122818336ULL, 8413660936055953583ULL,  244309246839733166ULL, // 4039
 5691018297570582295ULL, 3214623493731743950ULL, 5173087795859351739ULL, 4653890391451816575ULL,  314914677853388460ULL,  135065444429288697ULL, 4219613860047955585ULL, 4677541836078704101ULL, // 4047
 8783000588334687555ULL, 1525067579425779207ULL, 4519769206120649041ULL, 7169002588837913583ULL, 7462911010593458023ULL, 3420291568426609170ULL, 6555094910391502599ULL,  976900413942066964ULL, // 4055
 8632457234517543113ULL, 5797372846054778384ULL, 7657862659681441930ULL, 1562177940687748799ULL, 3822526073565729245ULL, 5424677802779306922ULL, 1803401783623699260ULL, 6420815368686302430ULL, // 4063
 4462698342128120434ULL, 3822961133974200997ULL, 6617903051397876932ULL, 1887648796421724617ULL, 4130245251210778532ULL, 2287269900223902787ULL, 8972541184409643420ULL, 4484709293707330761ULL, // 4071
 7455694223987264314ULL, 3740427340887237610ULL, 2286601299264185192ULL, 4639590151788952315ULL, 6999848660249572962ULL, 4927895278178758051ULL, 1719743517569234996ULL,  942908742122107422ULL, // 4079
  847849523415074150ULL, 5941537375386316393ULL, 6534461562053647191ULL, 3099822565242218071ULL, 3913754499801598990ULL, 2903302896862187942ULL, 8651262783927057905ULL, 2821177994721585168ULL, // 4087
 8446722293476852041ULL, 3550397787461151984ULL, 2640838580329033379ULL, 7619078928716175863ULL, 9030883856963587728ULL, 9220565649744586404ULL, 5448940780050442780ULL, 7709697203817853291ULL  // 4095
};

}  // namespace KCChess


// END {{{1   
// vim:shiftwidth=4:softtabstop=4:expandtab:foldmethod=marker
